EatyGuy Version 10: The Baddy Construction Kit

The ultimate version of EatyGuy—version 10—will act as an example of a minimalistic scripting interface exposed to users who can control baddy behavior. Although EatyGuy itself won’t provide a sandboxed environment, it will illustrate an interesting use case for which sandboxing is useful. It also will showcase the fact that, even in the world of a single app, there can be multiple Lua interfaces as seen by multiple users. (Don’t worry: although sandboxing isn’t part of EatyGuy, it will be covered later in this chapter.) Imagine, for example, that the different files of EatyGuy were written by coders with different roles. The writers of eatyguy10.lua saw eatyguy10.c as a game engine that provides appropriate data, such as keyboard input, and superclasses like Character.lua; these game engine components can be used to create a game in Lua. On the other hand, suppose that there were a separate set of people writing scripts to control baddies, an ability that we’ll cover in detail in this section.

In version 9 of EatyGuy, the behavior of baddies was determined by the method Baddy:move_if_possible() defined in Baddy.lua. Each baddy in version 9 generally moves along straight lines and turns in random directions when appropriate. They have no built-in tendency to move closer to EatyGuy, and this puts a damper on the game’s dramatic tension.

We could resolve this by writing more sophisticated enemy behavior code. But why do any work when you can simply tell someone else to do it for you? That’s the approach we’ll take by writing the UserBaddy class as a subclass of Baddy.

A UserBaddy instance will do the things a Baddy already did: it will hold all the state of the baddy, be able to draw the baddy, and be able to control how it moves around the maze. The difference is that a UserBaddy will also accept the name of a Lua script that will control the baddy’s movement. This control is achieved by letting the user write a function of this form:

local function choose_direction(baddy, possible_dirs,
                                grid, player)

  -- Work to choose a direction to go in.

  return chosen_direction
end

This function receives the UserBaddy instance (called baddy), a sequence of possible directions, the grid from eatyguy10.lua which encodes the walls and open spaces of the maze, and the Player instance that provides the position of the player. Each direction is a Pair instance, which was introduced in Chapter 4; for example, the direction indicating that EatyGuy can move to the right—in the positive x direction—would be instantiated by calling pair {1, 0}.

At this point, there are a ridiculous number of things that could go wrong. Handling those things is the point of this chapter, so let’s take a look at them:

• The user could return a direction it isn’t possible to move in; for example, because it makes EatyGuy head into a wall.

• The user could return a nonsense value such as the string 'tasty anchovies' or other values that defy both common and culinary logic.

• The user could use all of your system’s memory.

• The user could write an infinite loop.

The first two items—invalid return values—can be handled by checking the return value after each call to the user’s choose_direction() function. The last two items—devouring system resources willy-nilly—will be addressed later in this chapter.

Temporarily putting aside the resource-devouring concerns, let’s take a look at how we can implement UserBaddy itself. We want this class to be a special type of Baddy, so we’ll inherit from that class. To reflect this, and to accept the new script parameter, the constructor can be built like so:

-- The start of UserBaddy.lua

local Baddy = require 'Baddy'

local UserBaddy = Baddy:new({})

-- Set up a new baddy.
-- This expects a table with keys {home, color, chars, script}.
function UserBaddy:new(b)
  assert(b)  -- Require a table of initial values.
  b.pos           = b.home
  b.dir           = {-1, 0}
  b.get_direction = loadfile(b.script)()
  self.__index    = self
  return setmetatable(b, self)
end

Except for the line that calls loadfile(), this constructor is similar to Baddy’s constructor. Lua’s loadfile() function accepts a filename, parses that script, and returns a function that will run the script when called. We define b.get_direction by calling loadfile() and then immediately calling its return value on the same line. The result is that b.get_direction contains the first return value from the script. In other words, we expect the user script to act like this:

-- Skeleton of an example user script.

local function choose_direction(baddy, possible_dirs,
                                grid, player)

  -- Work to choose a direction to go in.

  return chosen_direction
end

return choose_direction

This way, the value of b.get_direction is the user’s choose_direction function. Because it accepts a Baddy instance as its first parameter, we can even call it from a UserBaddy method with colon syntax, as in self:get_direction().

To change the behavior of a Baddy, we need only to override a single method: move_if_possible(). Our new version of this method will take the following steps:

1. Build the possible_dirs sequence by checking in which directions EatyGuy can move.

2. Call self:get_direction(), passing in possible_dirs as well as the maze data (in grid) and the player’s location.

3. Check whether the returned value is valid; if not, replace it with a valid direction.

4. Update self.pos and self.old_pos to effect the movement in that direction.

Here is the method itself, along with the helper function is_in_table(), and finishing up with the final return call of the module:

-- The rest of UserBaddy.lua

local function is_in_table(needle, haystack)
  for _, value in pairs(haystack) do
    if value == needle then
      return true
    end
  end
  return false
end

function UserBaddy:move_if_possible(grid, player)

  -- Determine which directions are possible to move in.
  local deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
  local possible_dirs = {}
  for _, delta in pairs(deltas) do
    if self:can_move_in_dir(delta, grid) then
      table.insert(possible_dirs, pair(delta))
    end
  end

  -- Call the user-defined movement function.
  -- The `self` value will become the first parameter sent in.
  self.dir = self:get_direction(possible_dirs, grid, player)

  if not is_in_table(self.dir, possible_dirs) then
    self.dir = possible_dirs[1]
  end

  -- Update our position and saved old position.
  self.old_pos = self.pos
  _, self.pos  = self:can_move_in_dir(self.dir, grid)
end

return UserBaddy

Notice that UserBaddy.lua made use of the pair() convenience function that was previously defined in eatyguy9.lua. Because this is such a universally useful function, version 10 of EatyGuy defines pair() (as a global function) directly in util.lua instead of in eatyguy10.lua. The file eatyguy10.c is the same as eatyguy9.c except for the fact that it loads eatyguy10.lua instead of eatyguy9.lua.

Although the UserBaddy class is now completely defined, it’s not yet used by EatyGuy. To change that, we need to make some relatively small changes to eatyguy10.lua to create UserBaddy instances instead of Baddy instances.

The main change is to update the few lines that define the baddy_info table in eatyguy.init(). Here is that section of modified code from eatyguy10.lua:

  -- Set up the baddies.
  local baddy_info = { {color = 1, chars = 'oo', pos = {1, 1},
                        script = 'a_user_baddy.lua'},
                       {color = 2, chars = '@@', pos = {1, 0},
                        script = 'a_user_baddy.lua'},
                       {color = 5, chars = '^^', pos = {0, 1},
                        script = 'a_user_baddy.lua'} }
  for _, info in pairs(baddy_info) do
    info.home = pair{(grid_w - 1) * info.pos[1] + 1,
                     (grid_h - 1) * info.pos[2] + 1}
    table.insert(baddies, UserBaddy:new(info))
  end

For that code to work, the statement

local UserBaddy = require 'UserBaddy'

is needed along with the other require() calls near the beginning of the file. The final change is to update our call to Baddy.move_if_possible() to include an added argument that provides the player’s location. Replace the old call, in update(), with this modified call:

baddy:move_if_possible(grid, player)

EatyGuy version 10 is almost fully operational. The only thing left to be done is for the user to write her custom script called a_user_baddy.lua.

-- a_user_baddy.lua
-- Return the dot product of vectors a and b.
local function dot(a, b)
  return a[1] * b[1] + a[2] * b[2]
end

local direction = pair {1, 0}
local num_turns = 0

-- The next function will return true when:
--  * The player can turn left or right; or
--  * the player can't go straight ahead.
-- Intuitively, a "turning point" is any good place to consider
-- moving in a new direction.
local function is_turning_point(possible_dirs)
  local backwards       = pair {-direction.x, -direction.y}
  local can_go_straight = false

  for i, possible_dir in pairs(possible_dirs) do
    if possible_dir == direction then
      can_go_straight = true
    elseif possible_dir ~= backwards then
      return true  -- We can turn left or right.
    end
  end

  -- If we get here, then turning left or right is impossible.
  return not can_go_straight
end

local function choose_direction(baddy, possible_dirs,
                                grid, player)

  -- If we can't turn and we can go straight, then go straight.
  if not is_turning_point(possible_dirs) then
    return direction
  end

  -- Every 5th turn is random.
  num_turns = num_turns + 1
  if num_turns % 5 == 0 then
    direction = possible_dirs[math.random(#possible_dirs)]
    return direction
  end

  -- Try to go toward the player in the other 4 out of 5 turns.

  local to_player = pair {player.pos[1] - baddy.pos[1],
                          player.pos[2] - baddy.pos[2]}
  local max_dot_prod = -math.huge

  for i, possible_dir in pairs(possible_dirs) do
    local dot_prod = dot(possible_dir, to_player)
    if dot_prod > max_dot_prod then
      max_dot_prod = dot_prod
      direction    = possible_dir
    end
  end

  return direction
end

return choose_direction

Scripts Gone Wild

Let’s examine a few dangerous things that user scripts might try to do.

Imagine that you’re running user-written scripts on a server you own. In this case, it would be bad if anyone could run arbitrary shell commands on your machine. However, if you give users access to the os module, they could run a command like this:

os.execute('rm proof_that_p_is_not_np.tex')

Even if you left out the os module, a lot of damage could be done through the io module alone, such as reading, editing, or destroying sensitive data. To give a simple example, here’s a nice way to fill up your disk:

f = io.open('afile', 'w')
while true do f:write('all work and no play
') end

Issues like these can partially be addressed by limiting access to the standard library, which we’ll see how to do in the next section. However, the string library is difficult to avoid given that it’s tied to every instance of a string in Lua. For example, a user could eat up about 10 GB of your system memory with the following assignment:

a_long_string = ('x'):rep(1e10)

Perhaps surprisingly, there is something we can do about this issue (besides killing the process), and that is the subject of the section “Managing Memory Use”.

A final gotcha is the gluttonous consumption of precious CPU cycles. For example, the following script will take a long time:

for i = 1, math.huge do
  print('the way of the future')
end

Long-running scripts are particularly pernicious because the entire point of letting users write scripts is to give them a fair amount of freedom. It’s also difficult to decide in advance whether a given script will ever halt, let alone deciding how long it will take.

Again, there is a surprisingly simple and useful approach that we can take to address this; This is the topic of the section “Managing CPU Use” toward the end of this chapter.

Controlling Library Access

Lua offers an easy way to eliminate access to portions of the standard library. For example, if you wanted to prevent a user from calling anything in the os module, you could simply use the statement:

os = nil

Assuming that there were no other references to the os table—and by default there aren’t any—the os module would no longer be available.

It’s also possible to simply not load some of Lua’s standard modules in the first place. A typical way to set up a fresh Lua state is to call the C API function luaL_openlibs(L) early on in the life of L. As mentioned in Chapter 1, the luaL_openlibs(L) function loads all of Lua’s standard library into the given Lua state. However, you can also load only the “base” library, which includes most of Lua’s built-in functions like print() or pairs(); here is the C function call to do that:

// The luaopen_base() function is declared in lualib.h.

int set_global = 1;
luaL_requiref(L, "_G", luaopen_base, set_global);

Table 6-1 provides a general description of the luaL_requiref() C API function.

luaL_requiref(L, <modname>,
              <openfn>,
              <global>)

Recall from Chapter 4 that Lua modules written in C come with a specially named luaopen_<modulename>() function that the Lua interpreter knows to call at runtime if your module is imported via require(). The luaL_requiref() function gives you a consistent way to perform the same action from C.

As a further example, if you wanted to also include the package, string, math, and table modules, you could use this C code:

// The luaopen_*() functions are declared in lualib.h.

luaL_requiref(L, "package", luaopen_package, set_global);
luaL_requiref(L, "string",  luaopen_string,  set_global);
luaL_requiref(L, "table",   luaopen_table,   set_global);
luaL_requiref(L, "math",    luaopen_math,    set_global);

The GitHub repo for this chapter contains an example file called library_subset.c that demonstrates how to run a script with varying levels of access to the standard library using this approach.

Managing Memory Use

Lua provides a great way to track or limit its use of dynamic memory: Basically, it never calls malloc() or free() directly. Instead, it calls a wrapper function that is responsible for the allocation and deallocation of memory. This is useful because it allows us to track exactly how much memory has been used as well as to preemptively take action when more memory is requested than we’re ready to give.

Lua works with this wrapper function by defining a function pointer type called lua_Alloc that can point only to C functions with a signature like this:

void *my_alloc(void *ud, void *ptr, size_t osize, size_t nsize);

I’ve taken these pithy argument names directly from Lua’s reference manual; they are meant to capture a user data, a pointer, an old size, and a new size, in that order. The job of a lua_Alloc function is to either allocate or deallocate memory based on the parameters it receives. If the value of ptr is NULL, nsize bytes are to be allocated and returned as a new pointer; otherwise, the size of the chunk pointed to by ptr is meant to be adjusted from osize bytes to nsize bytes, which might mean either allocating or deallocated depending on whether nsize is larger or smaller than osize. If nsize is zero, this is expected to act like a call to free(). You can indicate that an allocation failed by returning NULL, and Lua will be able to gracefully handle such an error (that is, it will raise a Lua error, and won’t crash the process).

If you don’t want to do anything special, your custom lua_Alloc function can be as straightforward as this:

void *my_alloc(void *ud, void *ptr, size_t osize, size_t nsize) {
  if (nsize) return realloc(ptr, nsize);
  free(ptr);
  return NULL;
}

In our case, we do want to be fancy-like, so we’ll write a more sophisticated lua_Alloc function that tracks the total number of bytes used and refuses to let that number exceed a maximum value that we choose. A fun way to demonstrate this ability is to create a custom Lua interpreter with capped memory. To do this, I’ll first implement a useful function called accept_and_run_a_line(L) in the C file interpreter.c. This function reads in a line of code from stdin and executes that code in the given Lua state, returning the value 0 when the end of input is detected (which can be achieved by typing control-D). Here’s the body of the function:

// Part of interpreter.c

int accept_and_run_a_line(lua_State *L) {

  char buff[2048];

  // Read input and exit early if there is an end of stream.
  printf("> ");
  if (!fgets(buff, sizeof(buff), stdin)) {
    printf("
");
    return 0;
  }

  // Try to run the line, printing errors if there are any.
  int error = luaL_loadstring(L, buff);
  if (!error) error = lua_pcall(L, 0, 0, 0);
  if (error) {
    fprintf(stderr, "%s
", lua_tostring(L, -1));
    lua_pop(L, 1);
  }

  return 1;
}

This function is declared in the header file interpreter.h. (As always, you can view or download the complete files from this book’s GitHub repository.) We’re now ready to create a full, memory-limited interpreter. Here’s the code:

// limit_memory.c
//

#include "interpreter.h"

#include "lauxlib.h"
#include "lua.h"
#include "lualib.h"

#include <stdio.h>
#include <stdlib.h>
#include <sys/errno.h>

long bytes_alloced = 0;
long max_bytes = 30000;  // You can choose this value.

void *alloc(void *ud,
            void *ptr,
            size_t osize,
            size_t nsize) {

  // Compute the byte change requested. May be negative.
  long num_bytes_to_add = nsize - (ptr ? osize : 0);

  // Reject the change if it would exceed our limit.
  if (bytes_alloced + num_bytes_to_add > max_bytes) {
    errno = ENOMEM;
    return NULL;
  }

  // Otherwise, free or allocate memory as requested.
  bytes_alloced += num_bytes_to_add;
  if (nsize) return realloc(ptr, nsize);
  free(ptr);
  return NULL;
}

void print_status() {
  printf("%ld bytes allocated
", bytes_alloced);
}

int main() {
  lua_State *L = lua_newstate(alloc, NULL);
  luaL_openlibs(L);

  print_status();
  while (accept_and_run_a_line(L)) print_status();

  lua_close(L);
  print_status();
  return 0;
}

What will happen when we try to use too much memory? Let’s find out by running limit_memory. The exact outputs depend on which version of Lua you’re using, although your output should be similar in spirit to mine; here are the values I got when I ran the following commands:

$ ./limit_memory
22299 bytes allocated
> x = 3
22732 bytes allocated
> print(x)
3
23353 bytes allocated
> long_string = ('x'):rep(10000)
[string "long_string = ('x'):rep(10000)..."]:1: not enough
  memory for buffer allocation
24481 bytes allocated
> ^D
0 bytes allocated

You can see that Lua itself used about 22 KB initially, perhaps to help store the standard library. The assignment x = 3 used 433 bytes—that’s quite a few to store the number 3! The print(x) statement hopefully convinces you that this is not all smoke and mirrors, and that we are indeed running a functioning interpreter. The next line fails, and it does so without exceeding our hardcoded memory limit of 30,000 bytes. Finally, when we leave the interpreter, it’s deeply satisfying to see that Lua deallocates every last byte that it allocated, and not a bit more.

Managing CPU Use

Just as Lua gave us a nice hook function to track and react to memory allocation requests, it also gives us a hook to track and respond to CPU use. There are a few differences, however. First, whereas a custom memory allocation function doesn’t cost a ridiculous amount of speed, adding a custom CPU-cycle hook will have more of an effect on performance. Luckily, you can fine-tune at least one parameter to help find a good trade-off between limiting CPU use and the performance cost of doing so.

Another difference is that the CPU-cycle hook is more reactive than proactive. In other words, the memory allocation function in the last section was able to take action before an allocation took place, whereas the hook function in this section can only take action after a certain amount of CPU time has already been consumed. Luckily, you can choose to react quickly so that this difference is small in practice.

Similar to the lua_Alloc type, Lua defines another function pointer type called lua_Hook. A lua_Hook function must have a signature like this:

void my_lua_hook(lua_State *L, lua_Debug *dbg);

The lua_Debug struct has fields for various bits of information about the current execution state of Lua, such as the line number being executed. We won’t examine the lua_Debug struct, but if you’re curious to learn about what it can provide, I recommend reading the section The Debug Interface in Lua’s online reference manual.

Recall from the last section that we never directly called our lua_Alloc function; instead, Lua called it for us. Our lua_Hook function will be the same—it’s up to us to give Lua a pointer to our hook function and tell it when we want our hook function to be called. We can set a hook in Lua by calling the (wait for it…) lua_sethook() function. An example call looks like this:

// hook() is our lua_Hook function.

int instructions_per_hook == 100;
lua_sethook(L, hook, LUA_MASKCOUNT, instructions_per_hook);

The general function of the lua_sethook() function is complex because the third argument—the one with the value LUA_MASKCOUNT in our example—can take on the combination of several different values that correspond to different events that might trigger the lua_Hook function to be called. The meaning of the last argument depends on the value of the third argument. In the preceding example, we’ve set up our lua_Hook function hook() to be called once every 100 instructions. The official Lua implementation is based on a virtual machine that runs a bytecode-compiled version of Lua at runtime. The term instruction here refers to a single bytecode instruction as executed by the virtual machine. It’s not the same as a CPU cycle, but is still a very small chunk of time.

We can use a hook to notice when the number of instructions used by a script has exceeded some limit that we choose. As soon as that limit is exceeded, we can throw a Lua error. Let’s see this in practice by implementing a CPU-limited interpreter. In the code that follows, the hook is called for every single instruction that the virtual machine executes. This will cause Lua to be much slower than it normally would. In practice, you can use a higher value of instructions_per_hook to find a good trade-off in terms of speed versus precise control over CPU usage.

Here’s the code for a CPU-limited Lua interpreter, reusing the interpreter.h and interpreter.c files introduced in the previous section:

// limit_cpu.c
//

#include "interpreter.h"

#include "lauxlib.h"
#include "lua.h"
#include "lualib.h"

#include <stdio.h>
#include <sys/errno.h>

int do_limit_instructions    =    1;
long instructions_per_hook   =    1;  // 100+ recommended.
long instruction_count       =    0;
long instruction_count_limit =  100;

void hook(lua_State *L, lua_Debug *ar) {

  instruction_count += instructions_per_hook;

  if (!do_limit_instructions) return;

  if (instruction_count > instruction_count_limit) {
    lua_pushstring(L, "exceeded allowed cpu time");
    lua_error(L);
  }
}

void print_status() {
  printf("%ld instructions run so far
", instruction_count);
}

int main() {
  lua_State *L = luaL_newstate();
  luaL_openlibs(L);
  lua_sethook(L, hook, LUA_MASKCOUNT, instructions_per_hook);

  print_status();
  while (accept_and_run_a_line(L)) print_status();

  lua_close(L);
  return 0;
}

Here’s an example use of this interpreter, which allows up to 100 instructions to be run freely:

$ ./limit_cpu
0 instructions run so far
> sum = 0
2 instructions run so far
> print(sum)
0
6 instructions run so far
> for i = 1, 1000 do sum = sum + i end
exceeded allowed cpu time
101 instructions run so far

It’s fun to see exactly how many instructions are used by every line!

There’s one last gotcha for this approach of limiting CPU use: it can be stymied by long-running C code. Your hook function is guaranteed to be run based on CPU usage within Lua’s virtual machine, but we’ve seen that Lua happily can and will call out to modules written in C. Lua has little control over the time taken by those C functions. If you want to maintain an effective cap on the running time of a script, you will also need to account for the time taken by individual C functions callable from Lua, such as by ensuring that all such functions are guaranteed to be sufficiently fast.

End == Nigh

That about does it for this book! We’ve covered a lot of interesting ground. We learned how Lua and C can call each other, how to create Lua classes in C, how to work with errors in Lua, and how to give users the freedom to write their own scripts that can be run in a C-created sandboxed environment. Along the way, we got to create two example layers of Lua API: one layer between the simple game engine set up by eatyguy10.c and the game script eatyguy10.lua, and the second layer between the game script and user-written scripts to define baddy behavior. This reflects layers that might exist between different developer roles, and illustrates just a few of the use cases you’re now ready to take on.

I hope you’ve had as much fun reading this book as I did writing it!