⚪️ Mutz ⚪️

Revealing Lua's libc Dependency using Tree-Sitter

Author: Jack DeVries

Mutz aspires to be a runtime for Lua which can run in an extremely wide variety of environments, taking advantage of the Zig build system. To achieve this, it’s important for Mutz to embed Lua in a fashion which minimizes dependencies and maximizes future flexibility. A major crossroads early in the project is thinking through how Mutz should run in the browser.

This is the first part in a series to deep-dive the interplay between Lua, WASM, libc, emscripten, and Zig. In general, the goal is to get Lua running in a web browser, and to evaluate whether a useful flavor of Lua can run on a WASM freestanding target without libc.

Zig and Lua

Lua is known for being a very popular programming language, complete for pretty sophisticated programs, simple, and easy to embed. natecraddock/ziglua helped me get started with running Lua programs from Zig, and the implementation of ziglua helped me learn how to use the Zig build-system to compile and link Lua. In the Mutz repo (still private for now), I added ziglua and was thrilled to run a Lua program inside my Zig program! I was also surprised when print(1 + 1) “just worked ™.” I also knew that spelled trouble. How did those bytes make their way from Lua to my terminal STDOUT without me doing anything explicit?

Lua and libc

When Lua was created, it was built with the assumption that anywhere you may run code, you’d have libc available. The initial use-cases that Roberto Ierusalimschy, Luiz Henrique de Figueiredo, and Waldemar Celes were thinking about when it was created were data processing. First, for industrial users; think: simulations for oil companies. Later, for general purpose data manipulation in the context of graphics programming 1. In any case, people wanted to run Lua on a POSIX-like system where your day-to-day looks like launching the program from a terminal, reading from files or STDIN, and writing to files or STDOUT/STDERR. Early on, Lua got a strategic benefit from targeting the platform that libc provides. Way back in 1993, Lua ran on Windows 3.1, Macintosh, and “all flavors of Unix.”

This was happening at the dawn of GUI-based computing and way before the internet, smartphones, and everything else. “A computer” was a device which did computation. It took input data and mapped it to output data. The only major transition that had happened at that point was from punched-card mainframe computing to time-sharing Unix. The personal computing revolution was underway at the time, but the thesis there was really to take that terminal experience you got from the university or corporate time-sharing system and get it into your home. libc supported these use-cases because it includes basic facilities for interacting with files, input streams, output streams, the network, and other low-level operating system primitives.

Revealing Lua’s libc Dependency

Lua is written in C, and C has no namespacing. Remember, the Lua codebase is one of the most commonly embedded C codebases, meaning that others compile it into their own C programs. As a result, the Lua codebase itself can’t have even one function with a generic name in it. If it did, it would risk colliding with unknowable names in others’ codebases into which Lua is being embedded. The typical coping mechanism for this dynamic in C codebases is to use one or more common prefixes. In Lua’s case, the prefixes are lua and l_.

# snippet from lauxlib.h; notice every function has the "lua" prefix.
LUALIB_API int (luaL_getmetafield) (lua_State *L, int obj, const char *e);
LUALIB_API int (luaL_callmeta) (lua_State *L, int obj, const char *e);
LUALIB_API const char *(luaL_tolstring) (lua_State *L, int idx, size_t *len);
LUALIB_API int (luaL_argerror) (lua_State *L, int arg, const char *extramsg);
LUALIB_API int (luaL_typeerror) (lua_State *L, int arg, const char *tname);
LUALIB_API const char *(luaL_checklstring) (lua_State *L, int arg,

To start interrogating Lua’s libc dependency in more detail, I’ll enter a temporary directory, download Lua’s source-code, and unpack it.

# go to a temporary directory
cd "$(mktemp -d)"
# download the Lua 5.5 source-code
curl \
    --silent \
    --location \
    --output lua.tgz \
    https://www.lua.org/ftp/lua-5.5.0.tar.gz
# unpack the tarball
tar -xzf lua.tgz
# go into the src directory
cd lua-5.5.0/src

The code snippet above and the ones that follow are bash. They’ll work on any Linux or macOS terminal. Or, on Windows via WSL 2 or Cygwin 3. Feel free to follow-along!

We’ll use Tree-sitter 4 queries to enumerate function definitions, macro definitions, and function calls. In the end, thanks to C’s lack of namespacing, we can filter out function and macro definitions from function calls to get a view into all external calls, which will be into libc.

Store the query for all function definitions in query_function_definitions.txt:

cat <<EOF > query_function_definitions.txt
(function_definition
  declarator: [
    (function_declarator
      declarator: (identifier) @name)
    (pointer_declarator
      declarator: (function_declarator
        declarator: (identifier) @name))
  ])
EOF

Store the query for all macro definitions in query_macro_definitions.txt:

cat <<EOF > query_macro_definitions.txt
(preproc_def name: (identifier) @name)
(preproc_function_def name: (identifier) @name)
EOF

Store the query for all function calls in query_function_calls.txt:

cat <<EOF > query_function_calls.txt
(call_expression function: (identifier) @name)
EOF

Now that all the queries are prepared, we can use the tree-sitter CLI 5 to execute each query and store the output in more .txt files.

for query in function_definitions macro_definitions function_calls
do
    tree-sitter query "query_${query}.txt" *.c *.h \
        | grep 'text:' \
        | sed 's/.*text: `\(.*\)`/\1/g' \
        > "${query}_output.txt"
done

Finally, we’ve collected our bags of strings from Lua.

We can remove function and macro definitions from function calls:

grep -Fxvf function_definitions_output.txt < function_calls_output.txt \
    | grep -Fxvf macro_definitions_output.txt \
    | sort \
    | uniq -c \
    | sort -rn \
    | column -c 80

This leaves us with a rough list of every “external” function call in Lua. That is, calls to functions that are not defined elsewhere in Lua’s codebase:

    184 printf			      2 iscntrl
     30 strchr			      2 isalpha
     26 strlen			      2 getgclist
     22 memcpy			      2 fwrite
     14 strcmp			      2 free
     10 va_arg			      2 fgets
      8 strspn			      2 fflush
      7 isdigit			      2 dlopen
      7 getc			      2 dlerror
      7 checkstackp		      1 wf
      6 memcmp			      1 tmpfile
      5 sweepgen		      1 strrchr
      5 getenv			      1 strftime
      5 fprintf			      1 sprintf
      5 fopen			      1 sigemptyset
      5 exit			      1 sigaction
      4 strerror		      1 setvbuf
      4 strcpy			      1 setlocale
      4 memchr			      1 rename
      4 fclose			      1 remove
      4 dlsym			      1 realloc
      4 correctgraylist		      1 mktime
      3 va_start		      1 lua_atpanic
      3 va_end			      1 isupper
      3 toupper			      1 ispunct
      3 time			      1 isprint
      3 pushvfstring		      1 isgraph
      3 lua_rawlen		      1 freopen
      3 isalnum			      1 fputs
      3 getupvalref		      1 findlast
      3 fread			      1 feof
      3 ferror			      1 dlclose
      2 ungetc			      1 difftime
      2 tolower			      1 clock
      2 sweeptolive		      1 clearerr
      2 sweeplist		      1 catch
      2 strstr			      1 allocf
      2 strpbrk			      1 abs
      2 strncmp			      1 abort
      2 memset			      1 LoadLibraryExA
      2 lua_numbertocstring	      1 GetProcAddress
      2 luaL_newstate		      1 GetModuleFileNameA
      2 luaL_len		      1 GetLastError
      2 isxdigit		      1 FreeLibrary
      2 isspace			      1 FormatMessageA
      2 islower

This isn’t a perfect extraction. lua_atpanic and sweeptolive, for example, are not libc functions. They show up because some Lua functions are defined using this syntax which we didn’t bother querying for:

static GCObject **sweeptolive (lua_State *L, GCObject **p) { /* ... */ }

Drilling Down on libc Calls

We can recycle the file from before which stores the query to grab all function calls: query_function_calls.txt. Last time, we dumped all function calls across all files into one flat list. This time, we’ll:

  1. loop over each of Lua’s source files,
  2. run the query on each file, and
  3. store the file name alongside each function call.

We’ll gather our results in an output file: function_calls_by_file.txt:

rm -f function_calls_by_file.txt
for file in *.c *.h
do
    tree-sitter query "query_function_calls.txt" "${file}" \
        | grep 'text:' \
        | sed 's/.*text: `\(.*\)`/\1/g' \
        | xargs -I {} echo "${file} {}" \
        >> "function_calls_by_file.txt"
done

As before, we can subtract macro and function definitions from function calls, but this time we’re left with calls by file. We remove the grep -x flag which means that partial matches of lines from macro_definitions_output.txt in function_calls_by_file.txt will be filtered out. Matches will be partial since function_calls_by_file.txt stores the file name and function name side-by-side. I double-checked that macro_definitions_output.txt and function_definitions_output.txt don’t have any very short strings which might filter out calls to libc. There are single-letter macros in the Lua source, but they’re uppercase and all libc functions I know of are entirely lowercase, so I think that won’t cause an issue.

# Subtract macro and function definitions from function-calls-by-file to yield
# libc calls by-file.
grep -Fvf function_definitions_output.txt < function_calls_by_file.txt \
    | grep -Fvf macro_definitions_output.txt \
    | awk '{ print $1 }' \
    | sort \
    | uniq -c \
    | sort -rn \
    | column -c 80

Here’s the output:

23 lauxlib.c            13 ldblib.c              2 lvm.c
20 lstrlib.c            11 loslib.c              2 ldebug.c
18 lua.c                 9 lgc.c                 1 ltablib.c
16 loadlib.c             7 luac.c                1 lstring.c
15 lobject.c             4 ldo.c                 1 lstate.c
14 liolib.c              4 lbaselib.c            1 lcode.c

Run wc -l at the end of the previous pipeline instead of column -c 80 to count the number of files with one or more libc calls:

grep -Fvf function_definitions_output.txt < function_calls_by_file.txt \
    | grep -Fvf macro_definitions_output.txt \
    | awk '{ print $1 }' \
    | wc -l

18 Lua files call out to libc. Meanwhile, on the denominator, ls *.c *.h | wc -l shows that Lua has 61 total files.

Takeaway: there are a lot of Lua source files which don’t touch libc at all.

Cases we Can Eliminate

Some libc dependencies are more necessary than others. strchr, for example, locates the first occurrence of a character in a string. In GNU libc, it’s about 10 lines of code (not counting platform-specific optimizations) 6. It turns that there are many items surfaced in our investigation so far that we can eliminate at this stage:

Simple Cases

Many of the libc functions that Lua depends on are “simple.” My criteria here are:

The list of simple functions is:

Memory Allocation

Lua depends on only two libc memory management functions:

Lua also exposes a cool API to allow the user to control Lua’s memory allocator. The lua_Alloc interface is public in lua.h:

/*
** Type for memory-allocation functions
*/
typedef void * (*lua_Alloc) (void *ud, void *ptr, size_t osize, size_t nsize);

Then, a function pointer to the memory allocator is the first field in Lua’s global state (lstate.h):


/*
** 'global state', shared by all threads of this state
*/
typedef struct global_State {
  lua_Alloc frealloc;  /* function to reallocate memory */
  // ...
}

When Lua state is initialized, a user-controlled function pointer can be passed in, which overrides Lua’s default memory allocator. All together, even though libc memory allocation calls show up in the Lua source, it’s easy to customize. In practice Lua certainly could run on an arena allocator operating on a fixed-size buffer in environments where dynamic memory allocation is unavailable.

Really Basic System Interaction

A host runtime can stop or recover as soon as these are called regardless of environment.

Compiler Intrinsics

Compiler intrinsics around variadic functions 7 act like macros. Maybe they really are macros; I’m not sure. Either way, they won’t make it to runtime, so we don’t need to worry about them here:

Lua Stuff

Our search methodology was imperfect. All of the Lua stuff that slipped through can be manually filtered out now:

Windows Stuff

I know that Lua runs on platforms other than Windows. I’m going to ignore these calls into win32 APIs. Probably, when we’re not compiling Lua for Windows, it’ll switch to other libc functions instead, which are otherwise in-scope for this analysis.

printf

printf is the dominant libc call and I’ll eliminate it here by just acknowledging: yeah, that’s a thing. printf absolutely is not simple; it’s actually a secret virtual machine 8! While a full and correct printf implementation is quite hard, it would be easy to write a wrong poor man’s printf which did the job well enough.

I’m basically content to set this aside as an unsolved problem at this stage and focus on the other parts.

We can ignore it and its cousins;

Things to Ignore

The grand total set of things to ignore:

cat <<EOF > manual_filter.txt
FormatMessageA
FreeLibrary
GetLastError
GetModuleFileNameA
GetProcAddress
LoadLibraryExA
abort
abs
checkstackp
correctgraylist
exit
findlast
fprintf
free
getgclist
getupvalref
isalnum
isalpha
iscntrl
isdigit
isgraph
islower
isprint
ispunct
isspace
isupper
isxdigit
luaL_len
luaL_newstate
lua_atpanic
lua_numbertocstring
lua_rawlen
memchr
memcmp
memcpy
memset
printf
realloc
sprintf
strchr
strcmp
strcpy
strerror
strlen
strncmp
strpbrk
strrchr
strspn
strstr
sweepgen
sweeplist
sweeptolive
tolower
toupper
va_arg
va_end
va_start
wf
EOF

Things to Not Ignore

Process of elimination is done. Next time, we’ll even-deeper-dive on what’s left to complete this analysis and determine whether a useful flavor of Lua can run without libc.

grep -Fxvf function_definitions_output.txt < function_calls_output.txt \
    | grep -Fxvf macro_definitions_output.txt \
    | grep -Fxvf manual_filter.txt \
    | sort \
    | uniq -c \
    | sort -rn \
    | column -c 80

For next time, those are:

7 getc                  2 fgets                 1 remove
5 getenv                2 fflush                1 mktime
5 fopen                 2 dlopen                1 freopen
4 fclose                2 dlerror               1 fputs
4 dlsym                 1 tmpfile               1 feof
3 time                  1 strftime              1 dlclose
3 pushvfstring          1 sigemptyset           1 difftime
3 fread                 1 sigaction             1 clock
3 ferror                1 setvbuf               1 clearerr
2 ungetc                1 setlocale             1 catch
2 fwrite                1 rename                1 allocf

Assets

You can download the full bash script containing all snippets from this post here.

Citations

  1. The evolution of an extension language: a history of Lua.

  2. WSL is Windows Subsystem for Linux. It allows you to run a full virtualized Linux OS embedded within your Windows OS.

  3. Cygwin is a POSIX compatability layer for Windows. It allows software like bash to compile and run on Windows.

  4. Tree-sitter is a parser generator tool and an incremental parsing library.

  5. Tree-sitter can be used on the command-line using its CLI. You’ll need to install the CLI and setup the C parser to follow-along. I might detail this in a future post but for now you’ll need to read the friendly Tree-sitter manual. If you can run tree-sitter dump-languages and you see the C parser in the output then you’re ready to proceed.

  6. The GNU libc implementation of strchr looks like strchr => __strchrnul => find_zero_eq_all => find_zero_all plus some macros for pointer alignment and applying the bitmasks returned from the find_zero_* functions. Of course, there are also hand-optimized platform-specific implementations of the string-fza.h utils like sysdeps/arm/armv6t2/string-fza.h. It seems reasonable that the generic implementation would be about 10 lines of C after getting rid of the verboseness coming from DRY’ing into macros and layers of utility functions.

  7. Variadic function

  8. A very timely David Plumber video, “printf is Actually a Secret Virtual Machine - And a Giant Security Hole!” was released while working on this post.

← The Principle of Behavior/Mutation Separation
Case Study: luaL_loadfilex →