Archive for January, 2007

Writing Natives

Monday, January 29th, 2007

The good news: I’ve finally finished the extensive administration API. Sadly, I have not yet had the time to document it.

In the meantime, there is a new Wiki article up: Native Functions. As you will see, writing SourceMod natives is nearly identical to AMX Mod X. There are a few major differences:

  • cell is renamed to cell_t.
  • The params array is const.
  • Instead of an AMX structure, you get passed an IPluginContext interface which contains a large number of helper functions.
  • Retrieving strings from plugins is now a direct operation, because of our natively packed strings addition. As such, you can edit strings directly, rather than having to make a call to a secondary function. It also means there is no intermediate buffer which was previously a huge performance loss.

Overall, it’s similar enough to make AMX Mod X coders right at home; and having an object oriented context makes development much smoother.

SourceMod SDK Released!

Friday, January 26th, 2007

As promised, we’ve released the initial SourceMod SDK this week. Every night at midnight, the SDK is organized and uploaded from our private SVN repository. Click here for the SDK Site. It is publicly available.

As noted on the SDK Site, we also have binaries available. These are intended as developer only. They are of no use to the public, so please follow the directions to get access.

Nonetheless, this is a huge step forward for us. The original SourceMod couldn’t do anything. In its current state, SourceMod is a full plugin+extension system that works as-is. It’s just lacking the helper functions that are needed for it to be useful for Half-Life 2.

So, what’s left to do on SourceMod before it is publically ready? Quite a bit, but luckily now with the majority of work done, the rest should roll quickly.

  • Highest Priority
    • The Administration API is incomplete
    • The Translation API is not exposed
    • The Extension API does not resolve circular dependencies
  • High Priority
    • Create a Timer system
    • Create concmd/admin functions
    • Create convar functions
    • Finish admin-base.sp for reading the admin files
  • Medium Priority
    • Integrate the SQL API from AMX Mod X
    • Add network message creation
    • Add gameevent hooking

This is a rough list, but you get the idea. Everything except “Medium Priority” is a blocking issue. It will probably be a few more weeks until we can publically release. Luckily, this is not too far off from my initial estimate I gave before New Year’s.

Step by step, we’re getting there.

(Yes, the Administration article will have to continue on Monday. Sorry.)

What’s in a Handle?

Wednesday, January 24th, 2007

What does the Handle API available to extensions look like? You’ll be able to see in the upcoming SDK, but ahead of time: IHandleSys.h. On the implementation side, a lot goes into a single Handle. As it’s such an important API for extension writing, I’d like to touch upon its implementation. But, first let’s recap the permissions system, which you will need to remember:

Identities (explained earlier) are unique pointers assigned to major separated areas of SourceMod. Each plugin, extension, and a few important singletons create their own Identities. Identities are the owners of various shared resources, such as Handle types, Handles, interfaces, and native sets.

Like HL2 entities, Handles are stored in a giant static array (this array allows for 16K handles right now). Each handle is publicly addressed via a 32bit integer code. That code is actually two 16bit numbers. Bits 31-16 are a “serial number,” and bits 15-0 are the “handle index.” The index is an index into the internal Handle array. Each member of this array has the following properties:

  • type: An index into the Handle type table.
  • object: A generic pointer to the object this Handle holds.
  • serial: The serial number of the Handle. This is for validation.
  • refcount: The number of references to this Handle.
  • parent: If this Handle is a clone, this references the paren’t index.
  • state: Whether the Handle is freed or in use.
  • owner: The Identity which owns this Handle.
  • chain_next: The next Handle which is owned by the parent Identity.
  • chain_prev: The previous Handle which is owned by the parent Identity.

Next, what do types in the type array look like? Each type has the following properties:

  • dispatch: A pointer to an IHandleTypeDispatch object, which is responsible for destruction.
  • typeSec: Security permissions for the type index itself. This is associated with a parent Identity for “authentication.”
  • hndlSec: Security permissions for Handles created with this type.
  • opened: The number of Handles opened on this type.
  • name: The name of the type.

When reading a Handle from the Handle API, you must specify:

  • handle: The 32bit Handle code as described earlier.
  • type: The type to read the Handle as.
  • security: An optional struct containing the Identity that created the type, and the Identity that created the Handle.

Now, when reading a 32bit Handle code, the following steps occur:

  1. The index in bits 15-0 must be in the valid range (1 to 2^16-1).
  2. The Handle at said index must be in use (not freed).
  3. The Handle must have the same serial number as bits 31-16 in the 32bit code.
  4. The Handle must have the same type as the type you are trying to read as (a bit more complicated since types can have child types).
  5. If access to the type is restricted to only the Identity which created the type, the inputted type Identity must match the one originally given.
  6. If access to the Handle is restricted to only the Identity which created the Handle, the inputted Handle Identity must match the one in the Handle.
  7. Only after all of these steps succeed does a Handle read operation also succeed. Handle reads are not expensive, but they’re also not trivially cheap. If you only have to read once, it’s better.

    The Administration API article will continue on Friday.

Administration Interface (Part 1 of 2)

Monday, January 22nd, 2007

SourceMod’s administration interface is a big step over the AMX Mod X version. In this two part series, I’ll go over exactly how it’s configured from the user end, and how it’s designed to be extensible from the API side.

There were two problems to address in the AMX Mod X administrator configuration file format. These issues weren’t actual issues for most users. However, for that small elite group of high powered server operators, there were weak sides to the flat users.ini setup:

  1. Changing the access level of a command means editing the plugin source code and recompiling.
  2. There was no way to group users.

There were two ways to alleviate this. The first part is the admin_groups.cfg file, which you can view here. The Levels section defines the key area to solving the first problem: commands can be “overridden” with new access levels. How? When registering an administration command in SourceMod, the access and immunity checking is automatic (unlike with AMX Mod X). For example:

native RegisterAdminCmd(const String:cmd[],
                        const String:group[], 
                        ConsoleCommand:function, 
                        AccessLevel:defaultLevel);

The two new parameters over AMX Mod X’s register_concmd are group and defaultLevel. The former allows plugins to group commands into common tasks or ideas. For example, CS:S DM would have its commands in a “CS:S DM” group. And defaultLevel is for specifying the default access level of the admin command. This is where the Levels.Overrides section of admin_groups.cfg comes in: you can override the access levels of groups of or individual commands.

The group portion is fairly self explanatory. Groups are essentially permissions objects with single (but chainable) inheritance. The only special feature about groups is that you can pick and choose which other groups they are immune from. In this regard, immunity becomes a group property, not a user property, which is an important distinction. In AMX Mod X, immunity was simply an admin flag, and thus there was no hierarchy of admin immunity. (Of course, there was no admin hierarchy at all.)

The next step is the actual admins themselves, which is done in admins.cfg. The idea with this file is that each administrator has his or her own section in the file, rather than a single line of confusing parameters. There are two important properties to this:

  • auth – The method of authentication. This will be explained more in the API part of the article.
  • identity – The unique identity assigned to the authentication (for example, a Steam ID or IP address).

Lastly, each user can be assigned a flag string and membership to one or more groups (this lets you get around not being able to have a group inherit other groups).

Of course, we knew that the first thing people would say to this configuration format is: “It sucks! I want it to be easy.” Rest assured, the 99% of people who don’t want a confusing administration setup like this won’t have to use it! We’ve kept the old AMX Mod X users.ini format around in nearly the exact same style (we’re eliminating the stupid “connection flags” parameter). This should keep things easy for those who want a quick admin setup, and extensible for those who to make the most out of it. The file will be aptly named admins_simple.ini.

Now, here’s the kicker: the actual administration API is quite unrelated to the actual file format. In fact, the rules for flag inheritance and such are only a property of the parser, not the access checker itself. This is because with added complexity, there had to be sacrifices, and that sacrifice was making the API as simple as possible without ruining the idea. The API had to accommodate the simple users, the advanced users, and the advanced users who wanted their own custom MySQL schemas. How? Hopefully, I’ll get to explain this on Wednesday.

Writing Extensions Article

Friday, January 19th, 2007

There is now a very long article on the wiki entitled Writing Extensions. If you haven’t read the earlier articles, Extensions are SourceMod’s successor to AMX Mod X’s Modules. They allow you to write C++ plugins that use SourceMod and SourceMM API, with the ability to extend plugins with new events and functions.

We recently finished this Extension System, and it’s one of the bigger and more complicated pieces of SourceMod. This week we will be releasing both the SDK and the extensions we’ve made so far as examples. All of the articles for next week will be more on extension writing and the SourceMod API surrounding it.

I am pleased to say that with this, we are reaching very close to a usable beta of some sort. This beta will be for developers only (i.e. very thin on user features), but it will be a very complete development system. Once we have finished the base administration plugins, we’ll be able to do a public feature release.

On Late Loading

Wednesday, January 17th, 2007

Late loading is a touchy issue. There are three common points of time in a server’s loading process:

  1. When the Mod itself is loaded (MM:S, VSP plugins are loaded here)
  2. When the map is initializing (MM:S loads plugins here too)
  3. During the map (“late” loading)

Why is late loading a problem? Consider a plugin loaded 15 minutes into the map, right in the middle of gameplay. It has received none of the many important callbacks/events that happen on server/map initialization. Worse, there are most likely players in game, and if the mod has a “player manager” of sorts, it will have to do considerable work to back track and fire its own internal handlers for the player events it missed (such as connecting and getting put in server). Half-Life 2 makes this very difficult by being buggy with regard to IPlayerInfo.

In some cases, such as my Stripper:Source plugin, late loading doesn’t even make sense. Its sole function is to hook map loading! The original Metamod for Half-Life 1 addressed this by allowing plugins to specify a state in between “running” and “not running” – “waiting for changelevel.” This meant the plugin would not work until the map was changed.

We opted to not have this (yet) in Metamod:Source. Instead, plugins themselves receive a “late” parameter when they load, and using this, can either run alternative code to support late loading, or they can reject the load. Or, they can simply do nothing and wait for a map change to kick in.

For developers, being able to unload and reload a binary is extremely useful, especially when features like MSVC’s “Apply code changes and continue” don’t work. Taking this into account, we decided to half support late loading in SourceMod. The three rules:

  1. SourceMod itself will not late load. It waits for a mapchange to initialize.
  2. SourceMod plugins can be late loaded and late unloaded. This makes development much easier over AMX Mod X. Essential player connect callbacks are “replayed” for late plugins.
  3. SourceMod extensions can be late loaded and late unloaded, however, the extensions themselves can toggle this.

This should make late loading plugins as reliable as possible. If we allowed SourceMod to fully late load itself, it would be much more difficult to support plugins doing the same.

Text Parsing in SourceMod – Out-performing Valve

Monday, January 15th, 2007

For SourceMod, we decided to use Valve’s KeyValues file format for simplicity and familiarity. However, we didn’t use the provided KeyValues class. Why? To answer this question, let’s first take a look at the two major ways of writing text parsing API. There are “event based” parsers, and “tree based” parsers. Specifically, these are terms most commonly used with XML — but the KeyValues format has similar properties, such as nested sections, and so these parser patterns apply here.

A tree-based parser creates a big tree data structure out of the input text stream. The programmer then receives a pointer to the root node, and he can use this to recursively enumerate the tree (or just search for specific entries, depending on the contents). KeyValues is a tree based parser.

An event-based parser has no data structures. It reads the input character stream and fires user-provided callbacks for each major “event” encountered. It is then up to the programmer how to use these events. For example, events will be fired for:

  • Finding a new section starting or ending.
  • Find a new line.
  • Finding a key and value pair.

There are serious disadvantages to tree-based parsers. The immediate red flag you should see is that the tree structure must be allocated and built. If you don’t have a good allocator, you will wind up with a ton of small, unnecessary allocations for each node. On top of that, you waste memory. While both of these problems can be solved with a decent allocator, you also run into the problem of: what exactly does the programmer do with the tree structure? There are usually a few cases:

  1. You iterate over the tree and do a one-time operation/computation on all its contents. Then you delete the tree.
  2. You cache the tree and peek at its contents at a later time.
  3. You use the contents immediately by looking for a specific node, then delete the tree.
  4. You use the contents immediately by storing the data into a secondary structure, then delete the tree.

An event based parser is usually more ideal in all of these situations. Observe how for each method:

  1. All you’ve done is built a giant temporary structure that you discard. You could simply perform the operations as you receive the events, and remove the entire middle step of creating the structure. Iterating over the tree is fast, but creating the tree is unnecessary
  2. An event based parser isn’t always better here. However, if you are using a generic tree structure, peeking at it for a single entry may be very slow.
  3. This is even a bigger waste than #1. With an event based parser, you can stop parsing once you’ve hit the node you want. On top of that, you’ve removed the unnecessary tree structure AND eliminated a one-time recursive lookup in the tree.
  4. This is the worst of all. If you are going to use your own data structure, why bother building the tree in the first place? A better idea is to build the structure as you receive events.

So, why didn’t we use Valve’s KeyValues class? It’s a recursive tree parser. Worse yet, it’s generic. Everything and its mother in the SDK uses KeyValues, so it cannot possibly be optimized for each usage. A good example of this is in the Game Events system, which has name based lookup on event properties (a bad idea, as indexing them is not only more logical, but much, much faster).

At SourceMod, we wanted to show that not only were event based parsers better, but they allow you to quickly code alternative, faster data structures. At our arsenal, we had:

  • A highly optimized lookup class called a “double array trie.”
  • An optimized event-based parser for KeyValue-formatted files (source code provided below).
  • A fast lump allocator.

We took modevents.res from the cstrike folder of Counter-Strike: Source and wrote up a quick data structure using our pre-written, custom code library. Then we performed three benchmarks:

  1. Time to parse the file and load it into the respective data structure.
  2. Time to lookup two events in the structure – one in the middle, one at the beginning.
  3. Time to lookup a property in the event.

Our parser API: ITextParsers.h, CTextParsers.h, CTextParsers.cpp
Benchmark: benchmark.cpp

What happened?

[SOURCEMOD] Valve Read benchmark: 746622 clock ticks
[SOURCEMOD] SourceMod Read benchmark: 333864 clock ticks
[SOURCEMOD] Valve Lookup benchmark 1: 7740 clock ticks
[SOURCEMOD] SourceMod Lookup benchmark 1: 3339 clock ticks
[SOURCEMOD] Valve Lookup benchmark 2: 5391 clock ticks
[SOURCEMOD] SourceMod Lookup benchmark 2: 1827 clock ticks

In all three benchmarks, our code was more than twice as fast as Valve’s. Lesson: Always tune your data structures. One size does not fit all. Event-based parsers give you this full flexibility. As a bonus, you can implement a tree parser using an event parser (by building the tree during the events). Likewise, you can build an event parser using a tree parser (by firing an event for each iterated node), but that doesn’t make much sense.

SourceMod Debugger

Thursday, January 11th, 2007

The SourceMod Debugger is far less cludgy than its AMX Mod X counterpart, and I’ve been itching for the opportunity to discuss how it works. The debugger has one, and only one purpose: when your plugin fails to operate, it will display a “call stack,” or “backtrace,” of all the successive calls your plugin made in order for it to have reached the current line.

For example, a backtrace might look like:

Plugin "admin.smx" threw error (RTE19): "Player is not connected"
Failure occurred in native "GetClientAuthstring"
 [0] Line 25, public admin.sma::ValidateAdmin()
 [1] Line 64, public admin.sma::LoadAdmins()

This means that the plugin started on Line 64, and eventually called ValidateAdmin. Inside that function, it called GetClientAuthstring, which threw an exception (“run time error” in SourcePawn). Note: This information is only available for plugins running in debug mode.

How does this work? First, let’s take a look at the sp_context_t structure. This structure is analogous to the edict_t structure from Half-Life 1 and 2. It has specific variables for debugging purposes:

  • dbreak: After every few instructions, the JIT will call this function. This is the “Think” function of the debugger, and is used to track what position of the code the script is currently executing.
  • n_err: If a native fails, the error code it set is written here.
  • n_idx: If a native fails, the native’s index will be stored here.
  • frm: Position of the “stack frame,” which changes with each function call. (This is not specific to the debugger.)

For every plugin being debugged, we constantly maintain an active call stack, even if there are no errors. When the plugin does fail, we don’t have to do any advanced heuristics — the backtrace is already built for us.

Let’s look at the dbreak function. As mentioned, the JIT calls this every few instructions in order to update the debugger’s information. It passes in the context pointer, the current cip (code instruction index), and the current frm (current stack frame value). Every time this function “thinks,” the debugger’s current call stack information is re-analyzed and updated.

  1. If this is the first “Think” call for this execution run, set the top of our backtrace to the Code Index and Frame Value and do nothing more.
  2. If not, check the new Frame Value to our stored one at the top of the backtrace.
  3. If the Frame Values are equal, the plugin is still in the same function call. Simply store the new Code Index of the current position, then return.
  4. If the new Frame Value is greater than the old, the plugin left a function call. Pop a call off our backtrace, then return.
  5. If the new Frame Value is less than the old, the plugin started a new function call. Push empty values onto our backtrace, and go back to Step 1.

That’s the hardest part to the debugger (well, the hardest part is making that fast). Now, when any call to IPluginContext::Execute() fails, the Debugger automatically kicks in. How does this call fail? There are three major ways:

  • The plugin contains an internal flaw, for example indexing an array past its boundary, and it cannot be executed fully.
  • A library function decides to place the plugin in an erroneous state.
  • A native function throws an exception/run time error. This is done with ThrowNativeErrorEx() or ThrowNativeError().

When the debugger kicks in, it builds an IContextTrace object, which can be used to retrieve CallStackInfo structures, as well as error codes and the last native called. This data is then passed onto an IDebugListener class.

What implements the IDebugListener? That’d be the Logger. Thus, the debugger is completely automated. Whenever an error message fires, it goes straight into a logging routine which writes pretty output text. This is in stark contrast to AMX Mod X, which had a particularly nasty system of per-plugin debugging structures without any abstraction, resulting in spidery code that was very buggy for quite a few releases.

Note: Articles will on a Monday/Wednesday/Friday schedule.