Page MenuHomeFreeBSD

Optimize get_syscall() by avoiding string comparison.
Needs ReviewPublic

Authored by bdrewery on Aug 17 2016, 12:25 PM.

Details

Reviewers
jhb
Summary

Just compare the syscall number and its sysdecode ABI directly.

MFC after: 1 week
Sponsored by: EMC / Isilon Storage Division

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 4836
Build 4899: arc lint + arc unit

Event Timeline

bdrewery retitled this revision from to Optimize get_syscall() by avoiding string comparison..
bdrewery updated this object.
bdrewery edited the test plan for this revision. (Show Details)
bdrewery added a reviewer: jhb.
usr.bin/truss/syscalls.c
933–934

This is coming out in the next commit to fix unknown syscalls.

Why is this a list in the first place? Any issues just having a per-abi table indexed by a syscall number?

In D7547#156759, @mjg wrote:

Why is this a list in the first place? Any issues just having a per-abi table indexed by a syscall number?

See r288832 for why it is a list. Basically the former static array did not handle unknown syscalls. Unknown being ones that truss didn't know about since it has its own idea of the syscall table and what type of arguments each takes.

I don't think the original change was justified. The current syscall table ends at 549 and you can expect it will take several years for it to grow to anything remotely similar to 1024. That is, if you get a static table of 1024, a binary compiled now will handle legit syscalls from few generations of future binaries no problem. If there will be a syscall number going outside bounds of the table, you can tell the user to use truss from a similar time frame. If you see an unknown syscall within these bounds, you can just name it "unknown syscall <index>".

In D7547#156767, @mjg wrote:

I don't think the original change was justified. The current syscall table ends at 549 and you can expect it will take several years for it to grow to anything remotely similar to 1024. That is, if you get a static table of 1024, a binary compiled now will handle legit syscalls from few generations of future binaries no problem. If there will be a syscall number going outside bounds of the table, you can tell the user to use truss from a similar time frame. If you see an unknown syscall within these bounds, you can just name it "unknown syscall <index>".

Hardcoding any number would not be ideal. At Isilon we extend the table quite a lot and use the tail end to add some of our own syscalls. I had planned to explore using a hash table here but never got around to it. It hasn't seemed needed. This optimization was just found by accident when I was refactoring it for D7549 to fix unknown syscall handling.

What do you mean tail end? INT_MAX? If the offset you start putting your syscalls in is big, you can just keep a separate table for your own syscalls with indexes reduced by that offset.

Alternatively, you can have a static table with syscalls, have isilon syscalls appended immediately after that and special case that based on the offset. Then only actual unknown syscalls would be kept on a list.

And the last variant would have the static table for native freebsd syscalls and would maintain a list of all unknown syscalls. Then isilon syscalls, if it is problematic to put them in a table, can be also maintained on the list.

While I have not profiled truss, this kind of stuff sounds worrisome.

That said, I don't maintain the tool, so that's just my $0,03.

This approach doesn't really work since multiple ABIs share the same syscall (e.g. "read" is used by native, freebsd32, linux, and linux32 on amd64). This is why the look up is by name. The look up by name is used to map to a set of metadata that explains how to decode a system call's arguments (and is also used to hold the count for -c). For unknown system calls you do want to use the (abi, code) as the key, but I think that means that you construct a pseudo-name of something like '#<abi>-<code>', so '#freebsd-196' or some such. I do think you want to pass the thread info into get_syscall, but you should do something like:

if (t->cs.name == NULL)
    asprintf(&name, "#%s-%d", abi_name, code);  // note we don't really have an abi_name yet XXX
else
    name = t->cs.name;

/* Lookup via strcmp as we do now.   If you find a match and t->cs.name is NULL, free name and
    assign t->cs.name to the value in the found system call object. */

As far as performance considerations, the O(n^2) lookup on system call can be optimized by replacing the linked list with a hash table generating a hash key from the system call name (e.g. fnv, or whatever uipc_shm.c uses). I'd almost say you could just change truss to C++ and use std::unordered_map<>. OTOH, you can probably do something closer to what mjg@ suggests and replace the hash table by a double-layer array with the ABI as the first index and the code as the second index. The values stored in the table would be a pointer to the system call structures (not the raw structures), and on a "miss" you would resort to using strcmp to populate the table entry. That would give you O(1) lookup on repeat invocations of a system call. If your top-level array is an array of integer pointers you can just grow the secondary arrays as needed using realloc() if a code is larger than the current array size, though you can probably just start with an initialize size of 1024 which won't have to grow in practice anytime soon.