Author Archives: kevin

About kevin

I write the posts

Node’s `require` is dog slow

Posted on

Our test environment takes 6-9 seconds to load before any tests get run. I tire of this during the ~30 times I run the test suite a day,1 so I wanted to make it faster.

For better or worse, the API runs on Sails.js. Before running model/controller tests, a bootstrap file in our tests calls sails.lift.

require('sails').lift(function(err) {
    // Run the tests
});

This lift call generates about 400 queries against Postgres to retrieve database schema, that each look like this:

SELECT x.nspname || '.' || x.relname as "Table", x.attnum
as "#", x.attname as "Column", x."Type", case x.attnotnull
when true then 'NOT NULL' else '' end as "NULL",
r.conname as "Constraint", r.contype as "C", r.consrc,
fn.nspname || '.' || f.relname as "F Key", d.adsrc as "Default"
FROM (SELECT c.oid, a.attrelid, a.attnum, n.nspname, c.relname,
a.attname, pg_catalog.format_type(a.atttypid, a.atttypmod) as "Type",
a.attnotnull FROM pg_catalog.pg_attribute a, pg_namespace n,
pg_class c WHERE a.attnum > 0 AND NOT a.attisdropped
AND a.attrelid = c.oid and c.relkind not in ('S','v')
and c.relnamespace = n.oid and n.nspname
not in ('pg_catalog','pg_toast','information_schema')) x
left join pg_attrdef d on d.adrelid = x.attrelid
and d.adnum = x.attnum left join pg_constraint r on r.conrelid = x.oid
and r.conkey[1] = x.attnum left join pg_class f on r.confrelid = f.oid
left join pg_namespace fn on f.relnamespace = fn.oid
where x.relname = 'credits' order by 1,2;

I'm not really sure what those queries do, since Sails seems to ignore the schema that's already in the database when generating table queries. Since we use the smallest, safest subset of the ORM we can find, I tried commenting out the sails-postgresql module code that makes those queries to see if the tests would still pass, and the tests did pass... but the load time was still slow.

The next step was to instrument the code to figure out what was taking so long. I wanted to have the Sails loader log the duration of each part of the load process, but this would have required a global variable, and a whole bunch of calls to console.log. It turns out the Unix function ts can do this for you, if log lines are generated at the appropriate times. Basically, it's an instant awesome tool for generating insight into a program's runtime, without needing to generate timestamps in the underlying tool.

NAME
       ts - timestamp input

SYNOPSIS
       ts [-r] [-i | -s] [format]

DESCRIPTION
       ts adds a timestamp to the beginning of each line of input.

I set the Sails logging level to verbose and piped the output through ts '[%Y-%m-%d %H:%M:%.S]'. I pretty quickly found a culprit..

[2015-04-19 21:53:45.730679] verbose: request hook loaded successfully.
[2015-04-19 21:53:45.731032] verbose: Loading the app's models and adapters...
[2015-04-19 21:53:45.731095] verbose: Loading app models...
[2015-04-19 21:53:47.928104] verbose: Loading app adapters...
[2015-04-19 21:53:47.929343] verbose: Loading blueprint middleware...

That's a 2 second gap between loading the models and loading the adapters.

I started adding profiling to the code near the "Loading app models..." line. I expected to see that attaching custom functions (findOne, update, etc) to the Sails models was the part that took so long. Instead I found out that a module called include-all accounted for almost all of the 2.5 seconds. That module simply requires every file in the models directory, about 30 files.

Further reading/logging revealed that each require call was being generated in turn. I've found it, I thought, just use different CPU's to require them all at the same time, and see a speedup. Unfortunately, the require operation is synchronous in Node, and runs on one CPU, so the process can still only perform one require at a time.

I tried just loading one model to see how slow that would be. This script took an average of 700 milliseconds to run, on my high end Macbook Pro:

var start = Date.now();
require('api/models/Drivers');
console.log(Date.now() - start);

700 milliseconds to require a model file, and that file's dependencies! I can send a packet to and from New York 8 times in that amount of time. What the hell is it actually doing? For this I turned to good old strace (or dtruss, as it's ported on Macs). First start up a shell to record syscalls for any process that is called node.

# (You'll want to kill any other node processes before running this.)
sudo dtruss -d -n 'node' > /tmp/require.log 2>&1

Open up another shell session and run your little script that calls require and prints the startup time and then exits. You should have a few thousand lines in a file called /tmp/require.log. Here's what I found near the start:

   1186335 stat64("/Users/burke/code/api/api/models/node_modules/async\0", 0x7FFF5FBFE608, 0x9)             = -1 Err#2
   1186382 stat64("/Users/burke/code/api/api/models/node_modules/async.js\0", 0x7FFF5FBFE5B8, 0x9)          = -1 Err#2
   1186405 stat64("/Users/burke/code/api/api/models/node_modules/async.json\0", 0x7FFF5FBFE5B8, 0x9)                = -1 Err#2
   1186423 stat64("/Users/burke/code/api/api/models/node_modules/async.node\0", 0x7FFF5FBFE5B8, 0x9)                = -1 Err#2
   1186438 stat64("/Users/burke/code/api/api/models/node_modules/async.coffee\0", 0x7FFF5FBFE5B8, 0x9)              = -1 Err#2
   1186473 open("/Users/burke/code/api/api/models/node_modules/async/package.json\0", 0x0, 0x1B6)           = -1 Err#2
   1186501 stat64("/Users/burke/code/api/api/models/node_modules/async/index.js\0", 0x7FFF5FBFE5B8, 0x1B6)          = -1 Err#2
   1186519 stat64("/Users/burke/code/api/api/models/node_modules/async/index.json\0", 0x7FFF5FBFE5B8, 0x1B6)                = -1 Err#2
   1186534 stat64("/Users/burke/code/api/api/models/node_modules/async/index.node\0", 0x7FFF5FBFE5B8, 0x1B6)                = -1 Err#2
   1186554 stat64("/Users/burke/code/api/api/models/node_modules/async/index.coffee\0", 0x7FFF5FBFE5B8, 0x1B6)              = -1 Err#2
   1186580 stat64("/Users/burke/code/api/api/node_modules/async\0", 0x7FFF5FBFE608, 0x1B6)          = -1 Err#2
   1186598 stat64("/Users/burke/code/api/api/node_modules/async.js\0", 0x7FFF5FBFE5B8, 0x1B6)               = -1 Err#2
   1186614 stat64("/Users/burke/code/api/api/node_modules/async.json\0", 0x7FFF5FBFE5B8, 0x1B6)             = -1 Err#2
   1186630 stat64("/Users/burke/code/api/api/node_modules/async.node\0", 0x7FFF5FBFE5B8, 0x1B6)             = -1 Err#2
   1186645 stat64("/Users/burke/code/api/api/node_modules/async.coffee\0", 0x7FFF5FBFE5B8, 0x1B6)           = -1 Err#2
   1186670 open("/Users/burke/code/api/api/node_modules/async/package.json\0", 0x0, 0x1B6)          = -1 Err#2
   1186694 stat64("/Users/burke/code/api/api/node_modules/async/index.js\0", 0x7FFF5FBFE5B8, 0x1B6)                 = -1 Err#2
   1186712 stat64("/Users/burke/code/api/api/node_modules/async/index.json\0", 0x7FFF5FBFE5B8, 0x1B6)               = -1 Err#2
   1186727 stat64("/Users/burke/code/api/api/node_modules/async/index.node\0", 0x7FFF5FBFE5B8, 0x1B6)               = -1 Err#2
   1186742 stat64("/Users/burke/code/api/api/node_modules/async/index.coffee\0", 0x7FFF5FBFE5B8, 0x1B6)             = -1 Err#2
   1186901 stat64("/Users/burke/code/api/node_modules/async\0", 0x7FFF5FBFE608, 0x1B6)              = 0 0
   1186963 stat64("/Users/burke/code/api/node_modules/async.js\0", 0x7FFF5FBFE5B8, 0x1B6)           = -1 Err#2
   1187024 stat64("/Users/burke/code/api/node_modules/async.json\0", 0x7FFF5FBFE5B8, 0x1B6)                 = -1 Err#2
   1187050 stat64("/Users/burke/code/api/node_modules/async.node\0", 0x7FFF5FBFE5B8, 0x1B6)                 = -1 Err#2
   1187074 stat64("/Users/burke/code/api/node_modules/async.coffee\0", 0x7FFF5FBFE5B8, 0x1B6)               = -1 Err#2
      1656 __semwait_signal(0x10F, 0x0, 0x1)                = -1 Err#60
   1187215 open("/Users/burke/code/api/node_modules/async/package.json\0"0x0, 0x1B6)              = 11 0

That's a lot of wasted open()'s, and that's just to find one dependency.2 To load the single model, node had to open and read 300 different files,3 and every require which wasn't a relative dependency did the same find-the-node-module-folder dance. The documentation seems to indicate this is desired behavior, and it doesn't seem like there is any way around this.

Now, failed stat's are not the entire reason require is slow, but if I am reading the timestamps correctly in the strace log, they are a fair amount of it, and the most obviously wasteful thing. I could rewrite every require to be relative, e.g. require('../../node_modules/async') but that seems cumbersome and wasteful, when I can define the exact rule I want before hand: if it's not a relative file path, look in node_modules in the top level of my project.

So that's where we are; require for a single model takes 700 milliseconds, require for all the models takes 2.5 seconds, and there don't seem to be great options for speeding that up. There's some discouraging discussion here from core developers about the possibility of speeding up module import.

You are probably saying "load fewer dependencies", and you are right and I would love to, but that is not an option at this point in time, since "dependencies" basically equals Sails, and while we are trying to move off of Sails, we're stuck on it for the time being. Where I can, I write tests that work with objects in memory and don't touch our models/controllers, but Destroy All Software videos only get you so far.

I will definitely think harder about importing another small module vs. just copying the code/license wholesale into my codebase, and I'll definitely look to add something that can warn about unused imports or variables in the code base.

I'm left concluding that importing modules in Node is dog slow. Yes, 300 imports is a lot, but a 700ms load time seems way too high. Python imports can be slow, but as far as I remember, it's mostly for things that compile C on the fly, and for everything else you can work around it by rearranging sys.path to match the most imports first (impossible here). If there's anything I can do - some kind of compile option, or saving the V8 bytecode or something, I'm open to suggestions.

1. If you follow along with the somewhat-crazy convention of crashing your Node process on an error and having a supervisor restart it, that means that your server takes 6-9 seconds of downtime as well.

2. The story gets even worse if you are writing Coffeescript, since require will also look for files matching .litcoffee and .coffee.md at every level. You can hack require.extensions to delete these keys.

3. For unknown reasons, node occasionally decided not to stat/open some imports that were require'd in the file.

Liked what you read? I am available for hire.

Beware tech companies who tell you they don’t negotiate

Posted on

Reddit and Duck Duck Go recently announced that they are eliminating salary negotiations, in part to help even the playing field for men and women, since men are more likely to negotiate salaries than women.

Men negotiate harder than women do and sometimes women get penalized when they do negotiate. So as part of our recruiting process, we don’t negotiate with candidates," Pao said in the interview. "We come up with an offer that we think is fair. If you want more equity, we’ll let you swap a little bit of your cash salary for equity, but we aren’t going to reward people who are better negotiators with more compensation."

I am a little skeptical. It's fine for a company to announce this, but they lose nothing from announcing "we don't negotiate offers". The person you really need to ask is the person who has 5 offers from different tech companies. If they go to Reddit or Duck Duck Go and say, "I'll come work for you for another $5k / $10k with the same equity", are they turned down 100% of the time? If yes, then I'll believe a company with a stated policy that says "we don't reward negotiators".

Announcing "We give fair offers" is a smart move on behalf of a negotiator; it lends better credibility to whatever offer is on the table. It's just not in their best interest to disclose that they negotiate.

In my last round of job interviews, one company made me an offer, told me in strong words that "this offer is non negotiable", then ended up offering me both more salary and more equity.

I would also like to remind everyone that, within the last decade, six of the largest tech companies in the USA conspired to depress wages for engineering employees. I will repeat that last sentence. SIX OF THE LARGEST TECH COMPANIES IN THE USA ACTIVELY COLLUDED TO KEEP ENGINEERING SALARIES DOWN FOR FIVE YEARS. Steve Jobs, a person who many tech CEO's admire and try to emulate, threatened Sergey Brin because Google was trying to recruit Safari engineers.

Yes, Reddit and Duck Duck Go are not those companies, but if half of the National League teams are found colluding, I'm going to have a little skepticism when the Rangers tell me "this is the best offer you're going to get". I almost forgot, that example doesn't even work, because all of the MLB owners recently colluded to depress salaries as well. Given the history, as a tech employee you are wise to take anything tech employers say with a grain of salt.

I applaud Reddit and DDG for taking policy steps to address the gaps between pay for men and women. They may find that starting with a high offer helps them close candidates - great! But I am skeptical that "we don't negotiate" is true, or at least, we're not hearing it from the right party in the negotiation.

Liked what you read? I am available for hire.

“Invalid Username or Password”: a useless security measure

Posted on

"Invalid Username or Password": a useless security measure

Login attempts fail because computer users can't remember their email or didn't input the right password. Most websites on the Internet won't tell you which one is actually incorrect.

Amazon:

Amazon

Shoprunner:

Shoprunner

Hacker News:

HN

If you tell an attacker the email address is wrong, they'll try a different one. If you tell them the password is wrong, then an attacker knows that the username is correct, and can go on to try a bunch of passwords for that username until they hit the right one. So sites won't tell you which one is wrong, to try and avoid the information disclosure.

Unfortunately this assumes that there's no other way for an attacker to discover whether a username/email address is registered for a service. This assumption is incorrect.

99.9% of websites on the Internet will only let you create one account for each email address. So if you want to see if an email address has an account, try signing up for a new account with the same email address.

Here are all of the websites above, confirming that an account exists with my email address/username:

Amazon:

Amazon

Shoprunner:

Shoprunner

Hacker News:

HN

So what we've done by promoting "Invalid username or password" is made our login form UX much, much worse, without increasing the security of our product.

If people don't log in to your site every day (every site on the web except Facebook or Google), not remembering credentials is a huge barrier to accessing your site. Don't make it harder by adding a vague error message that doesn't increase your site's security at all.

But there's a tradeoff there between security and UX, I hear you say. I am trying to show you there is no tradeoff, as presented above; you are choosing between a better user experience and a worse user experience.

What should I do instead?

Here is an actual UX/security tradeoff: you can make the signup process email based. When someone attempts to sign up with an email address, you send them an email to complete the registration process. If they don't control the email inbox, they can't see whether the email address has an account already. This is much more arduous and requires two context switches (go into your email, avoid distraction, wait for email to arrive, click link in email, remember what you were doing on site). I don't recommend this, because of the context switches, though you can implement it.

Otherwise, accept that your login page and your signup pages are targets for malicious behavior, and design appropriately.

  • Rate limiting can go a fair way to preventing brute force attacks. To find email addresses, an attacker is going to need to try a lot of email addresses and/or a lot of passwords, and get a lot of them wrong. Consider throttling invalid login attempts by IP address or subnet. Check submitted passwords against a dictionary of common passwords (123456, monkey, etc) and ban that traffic extra hard. Exponential backoff (forcing attackers to try again after 1, 2, 4, 8, 16.. seconds) is useful.

  • Give guidance to users about creating strong passwords. Allow easy integration with LastPass or 1Password.

  • Add a 2-factor auth option to your website. Encourage users to use it.

  • Warn users about malicious behavior ("someone is trying to snoop your password") and contact them about suspicious logins.

Liked what you read? I am available for hire.

Profiling ZSH startup time

Posted on

Recently I had a very weird problem with iTerm where new login shells were being created with environment variables already present. Restarting my machine made the issue go away, and I wasn't able to reproduce it again.

But I got curious about how long ZSH spends in various parts of the startup process. A new /bin/bash login shell loads instantaneously and I was wondering why my ZSH startup was so slow, and if there was anything I could do to make it faster. My goal was to get to a command prompt in under 100 milliseconds.

What files run when you start a ZSH login shell?

In order, your machine will load/execute the following files when ZSH starts:

/etc/zshenv
~/.zshenv
/etc/zprofile
~/.zprofile
/etc/zshrc
~/.zshrc
/etc/zlogin
~/.zlogin

On my machine only /etc/zshenv (which adds paths in /etc/paths* to the $PATH variable) and ~/.zshrc actually existed, which simplified the problem somewhat.

I used the following two scripts to check execution time. First, this snippet logged the execution time of every command run by my startup script in ~/tmp/startlog.<pid>.

    PROFILE_STARTUP=false
    if [[ "$PROFILE_STARTUP" == true ]]; then
        # http://zsh.sourceforge.net/Doc/Release/Prompt-Expansion.html
        PS4=$'%D{%M%S%.} %N:%i> '
        exec 3>&2 2>$HOME/tmp/startlog.$$
        setopt xtrace prompt_subst
    fi
    # Entirety of my startup file... then
    if [[ "$PROFILE_STARTUP" == true ]]; then
        unsetopt xtrace
        exec 2>&3 3>&-
    fi

Essentially this prints the command that zsh is running before you run it. The PS4 variable controls the output of this print statement, and allows us to insert a timestamp each time we run it.

I then wrote a short python script to print all lines above a certain threshold. This is okay, but can show a lot of detail and won't show you if one line in your .zshrc is causing thousands of lines of execution, which take a lot of time in total.

Observations

At first I used the GNU date program in the PS4 prompt to get millisecond information about the time, however this program consistently used 3 milliseconds to run, so it got costly to run it thousands of times during system profiling.

The first thing you find is that shelling out is very expensive, especially to high-level languages. Running something like brew --prefix takes 50 milliseconds which is half of the budget. I found that Autojump's shell loader ran brew --prefix twice so I submitted this pull request to cache the output of that and run it again.

Another timing method

Ultimately what I want is to time specific lines/blocks of my zshrc, instead of get profiling information for specific lines. I did this by wrapping them in time commands, like this:

    { time (
        # linux
        (( $+commands[gvim] )) && {
            alias vi=gvim;
            alias svi='sudo gvim'
        }
        # set up macvim, if it exists
        (( $+commands[mvim] )) && {
            alias vi=mvim;
            alias svi='sudo mvim'
        }
    ) }

This will time commands in a sub-shell, which means that any environment variables set in the sub-shell won't be set in the environment. However the purpose is to get timing information and it's good enough for that.

Lazy loading

By far the worst offenders were the various "Add this to your .zshrc" scripts that I had added in the past - virtualenvwrapper, travis, git-completion, autojump, pyenv, and more. I wanted to see if there was a way to load these only when I needed them (I don't, frequently). Turns out there is! Most of these set functions in zsh, so I can shadow them with my own functions in a zshrc. Once the file with the actual function definition is sourced, it'll replace the shim and I'll be fine. Here's an example for autojump:

    function j() {
        (( $+commands[brew] )) && {
            local pfx=$(brew --prefix)
            [[ -f "$pfx/etc/autojump.sh" ]] && . "$pfx/etc/autojump.sh"
            j "$@"
        }
    }

Or for pyenv:

pyenv() {
    eval "$( command pyenv init - )"
    pyenv "$@"
}

Essentially on the first invocation, these functions source the actual definition and then immediately call it with the arguments passed in.

Conclusion

Ultimately I was able to shave my zsh startup time from 670 milliseconds to about 390 milliseconds and I have ideas on how to shave it further (rewriting my weirdfortune program in Go for example, to avoid the Python/PyPy startup cost). You can probably get similar gains from examining your own zshrc.

Liked what you read? I am available for hire.

Ready Player One and a Dystopian View of Future Oil Prices

Posted on

I read Ready Player One recently and I enjoyed it; it was a pretty fast read and I finished it in a day. It presents a view of the future where the possibilities allowed by a virtual reality world surpass those of the real world, so most people spend as much time as possible connected to a system called OASIS.

One part of the book's prediction of the future bothered me. The author describes the price of oil skyrocketing, causing the decay of American roads, and cities with cars stacked around their exteriors, as the unaffordable price of oil made them too expensive to drive.

This bothered me and my economics degree. People hugely value the ability to move around and travel for many reasons:

  • For reasons we cannot yet explain in-classroom teaching produces better results than online teaching, meaning the teacher and students need to travel to the same place (There's a study showing this result but I don't know where it is).

  • People migrate for work, to bring their skills to an area of the world where there's more demand for them, see for example the millions of Filipinos who work overseas. People will still need food delivered and haircuts and their plumbing fixed and their cars driven even if they spend twelve hours a day with a headset strapped to their face.

  • The same is mostly true of relationships and friendship bonding; the face to face time is a costly signal that helps show the other person you care and are committed to the relationship.

  • People enjoy traveling for tourism, to see beaches, mountains, etc. Sure virtual reality could put you on a beach and it might be "good enough" but a device that can replicate the feeling of the sand beneath your toes is still a ways away.

And many, many more; sure, virtual reality may chip away at the margins here but there still will be a vast demand for people to fly around the planet.

The vast demand means that there's a huge incentive for folks to figure out cost-effective ways to get around. If gas gets too expensive, we see people figure out ways to create gas from other minerals, as the large expansion of activity in North Dakota shows. Or there will be more of an incentive to figure out how to store solar energy to use at night, or more of an incentive to use electric power to get around, and we'd see more trains and less planes.

How can we turn this into a testable prediction? One obvious answer is to look at the price of oil. The author writes that the price will be sky-high, causing people to abandon their cars. Well another group of people bet on the price of oil every day. I tend to trust them more, because if they are wrong, they will lose tons of money.

Data from the CME Group indicates that the best prediction for the price of oil in December 2022 is $86.20, lower than it is today. Now, there are some caveats that would affect this. There are reasons to believe the futures price might be lower than the true price in 2026, because a buyer today is assuming risk and the seller is shedding it. On the flip side at least one source states that oil futures with long maturities tend to be priced higher than the actual price.

So that's the best prediction of the price of oil 8 years from now - about what it is today, not drastically higher. I would encourage anyone who thinks oil will be very expensive (including the author) to bet on that outcome, and profit from all of the people who currently think it will be cheap.

In general we look to science fiction authors for a vision of what the future will look like. In some places they may be better than average at predicting what the future will look like. But clearly in others, they're not.

Liked what you read? I am available for hire.

Hacking Roller Coaster Tycoon with Genetic Algorithms

Posted on

I used to play a ton of Roller Coaster Tycoon when I was a kid. I loved the game but I was never very good at making the roller coasters. They always felt too spread out, or too unnatural looking. As a ten year old I idly wondered about writing a computer program that was really good at playing the game. What sort of parks would it make? How would a computer approach the freedoms inherent in an empty park? What would we learn about the game engine from doing so?

A cool coaster

Sadly, this one wasn't generated by a computer

In case you're not familiar, Roller Coaster Tycoon is a amusement park simulation game most notable because the entire game was written in x86 assembler by Chris Sawyer.

Finally a few months ago, I had the tools and the free time available to work on this, and I made some progress toward writing a program that would generate cool looking roller coasters. Let's examine the parts of this program in turn.

Interacting with the Game

So let's say you have a program that can generate roller coasters. How do you actually put them in the game, or integrate them into your parks?

Fortunately, Roller Coaster Tycoon has a format for saving track layouts to disk. Even more amazingly, this format has been documented.

4B: departure control flags
4C number of trains
4D number of cars per train
4E: minimum wait time in seconds
4F: maximum wait time in seconds

Once you decode the ride data, it follows a format. Byte 0 stores the ride type - 00000010 is a suspended steel roller coaster, for example. Some bytes indicate the presence of flags - the 17th bit tells you whether the coaster can have a vertical loop. And so on, and so on.

To compress space, RCT used a cheap run-length encoding algorithm that would compress duplicates of the same byte. But once you encoded/decoded the file, it was super easy to get it running in the game.

So, great! I could write my coaster generator in any language I wanted, write out the file to disk, then load it from any of the parks.

Getting Track Data

There are a lot of track pieces in the game, and I needed to get a lot of data about each of them to be able to make assertions about generated roller coasters. As an example, if the track is currently banked left, which pieces are even possible to construct next?

A steep upward slope track piece increases the car height 4 units. A sharp left turn would advance the car 3 squares forward and 3 squares left, and also rotate the car's direction by 90 degrees. I had less than zero interest in doing this all by hand, and would probably make a mistake doing it. So I went looking for the source of truth in the game..

OpenRCT2

Literally the same week that I started looking at this, Ted John started decompiling the Roller Coaster Tycoon 2 source from x86 into C, and posting the results on Github. More importantly (for me), Ted and the source code actually showed how to read and decompile the source of the game.

The repository shipped with an EXE that would load the C sources before the x86 game code. From there, the C code could (and did, often) use assembler calls to jump back into the game source, for parts that hadn't been decompiled yet.

This also introduced me to the tools you use to decompile x86 into C. We used the reverse engineering tool IDA Pro to read the raw assembly, with a shared database that had information on subroutines that had been decompiled. Using IDA is probably as close as I will come to a profession in code-breaking and/or reverse engineering.

Most of the time with IDA involved reading, annotating the code, and then double checking your results against other parts of the code, the same way you might annotate a crossword puzzle. Other times I used guess and check - change a value in the code, then re-run the game and see what specifically had changed, or use debugging statements to see what went on.

So I started looking for the track data in the game. This turned out to be really, really difficult. You would have a hunch, or use the limited search capability in the game to search for something you thought should be there. Ultimately, I figured out where the strings "Too high!" and "Too low!" were being called in the engine, figuring that track height data would have been computed or used near those points.

This was only part of the solution - it turns out that track data is not stored in one big map but in several maps all around the code base. Some places store information about track bank, some store information about heights and it's tricky to compile it all together. Ultimately, I was able to figure it out by spending enough time with the code and testing different addresses to see if the values there lined up with the pre-determined track order.

Visualizing rides

With a genetic algorithm you are going to be generating a lot of roller coasters. I wanted a quick way to see whether those roller coasters were getting better or not by plotting them. So I used Go's image package to draw roller coasters. To start I didn't try for an isometric view, although that would be fun to draw. Instead I just plotted height change in one image and x/y changes in another image. Running this against existing roller coasters also revealed some flaws in my track data.

A fitness function

A good fitness function will have penalties/rewards for various pieces of behavior.

  • Is the ride complete?

  • Does the ride intersect itself at any points?

  • Does the ride respect gravity, e.g. will a car make it all the way around the track?

  • How exciting is the ride, per the in-game excitement meter?

  • How nauseating is the ride, per the in-game excitement meter?

The first two points on that list are easy; the last three are much more difficult. Finding the excitement data was very tricky. I eventually found it by getting the excitement for a "static" ride with no moving parts (the Crooked House) and searching for the actual numbers used in the game. Here's the function that computes excitement, nausea and intensity for a Crooked House ride.

sub_65C4D4 proc near
or      dword ptr [edi+1D0h], 2
or      dword ptr [edi+1D0h], 8
mov     byte ptr [edi+198h], 5
call    sub_655FD6
mov     ebx, 0D7h ; ''
mov     ecx, 3Eh ; '>'
mov     ebp, 22h ; '"'
call    sub_65E7A3
call    sub_65E7FB
mov     [edi+140h], bx
mov     [edi+142h], cx
mov     [edi+144h], bp
xor     ecx, ecx
call    sub_65E621
mov     dl, 7
shl     dl, 5
and     byte ptr [edi+114h], 1Fh
or      [edi+114h], dl
retn
sub_65C4D4 endp

Got that? In this case 0xD7 in hex is 215 in decimal, which is the ride's excitement rating. I got lucky that this value is static and not changed by anything, which meant I could search for it from outside the binary. This is then stored in the ride's location in memory (register edi), at the offset 0x140. In between there are a few subroutine calls, which shows that nothing is ever really easy when you are reading x86, as well as calls to functions that I have nothing besides hunches about.

Anyway, when you turn this into C, you get something like this:

void crooked_house_excitement(rct_ride *ride)
{
    // Set lifecycle bits
    ride->lifecycle_flags |= RIDE_LIFECYCLE_TESTED;
    ride->lifecycle_flags |= RIDE_LIFECYCLE_NO_RAW_STATS;
    ride->var_198 = 5;
    sub_655FD6(ride);

    ride_rating excitement  = RIDE_RATING(2,15);
    ride_rating intensity   = RIDE_RATING(0,62);
    ride_rating nausea      = RIDE_RATING(0,34);

    excitement = apply_intensity_penalty(excitement, intensity);
    rating_tuple tup = per_ride_rating_adjustments(ride, excitement, intensity, nausea);

    ride->excitement = tup.excitement;
    ride->intensity = tup.intensity;
    ride->nausea = tup.nausea;

    ride->upkeep_cost = compute_upkeep(ride);
    // Upkeep flag? or a dirtiness flag
    ride->var_14D |= 2;

    // clear all bits except lowest 5
    ride->var_114 &= 0x1f;
    // set 6th,7th,8th bits
    ride->var_114 |= 0xE0;
}

And we're lucky in this case that the function is relatively contained; many places in the code feature jumps and constructs that make following the code pretty tricky.

So this one wasn't too bad, but I got bogged down trying to compute excitement for a ride that had a track. The function gets orders of magnitude more complex than this. One positive is, as far as I can tell, excitement and nausea ratings are wholly functions of overall ride statistics like the vertical and lateral G-forces, and there's no accumulator per track segment.

Most of the computation involves multiplying a ride statistic by a constant, then bit shifting the value so it can't be too high/influence the final number by too much.

And sadly, this is where the project stalled. It was impossible to test the C code, because the track computation functions were buried four subroutines deep, and each of those subroutines had at least 500 lines of code. Decompiling each of these correctly, just to get to the code I wanted, was going to be a massive pain. There are ways around this, but ultimately I got back from vacation and had to focus on more pressing issues.

Conclusion

You can hack Roller Coaster Tycoon! There are a bunch of people doing interesting stuff with the game, including improving the peep UI, working on cross compilation (you can play it on Macs!), adding intrigues like the possibility of a worker strike, removing limitations based on the number of bytes (you can only have 255 rides, for example), and more.

It's been really fun having an utterly useless side project. I learned a lot about registers, calling conventions, bit shifting tricks, and other things that probably won't be useful at all, for anything.

I will definitely revisit this project at some point, hopefully when more of the game has been decompiled, or I might try to dig back into the x86/C more on my own.

Liked what you read? I am available for hire.

Use a VPN

Posted on

You should sign up for a VPN service! Yes you, the casual Internet browser. Here is why.

  • Any time you connect from your laptop/phone to a wireless network (SFO Wifi, Starbucks, etc), anyone else on that network can read all of your traffic over HTTP, to sites like Wikipedia, Netflix, YouTube, WebMD and more. This is not good.

  • Your ISP (Comcast, AT&T etc) can also read your HTTP traffic and throttle connections based on it. This is part of the reason for the Net Neutrality hubbub and the poor performance many people suffer when connecting to Netflix.

    When you use a VPN, all of your traffic is encrypted from your computer to your VPN service provider, and you should enjoy good speeds from there to the rest of the Internet.

  • In some cases, an ISP actually intercepts the response from the remote website and inserts its own ads or content. A VPN encrypts all of the traffic and makes this impossible.

  • You can use a VPN to route around location-based IP tracking; for example, if the Warriors are blacked out on NBA TV in your area, you can connect to a VPN server in New York to watch the game.

  • VPN's provide a better level of anonymity. In general, a VPN provider smushes all of its outbound and inbound traffic together so it's harder to track a specific set of requests back to you. Your ISP can no longer log your traffic.

It is pretty easy to set up a VPN for PC or Mac, and cheap (about the price of a coffee every month). I suggest you try it today!

Liked what you read? I am available for hire.

Nix: caveat emptor

Posted on

I'm setting up a new website, which gave me an excuse to try out Nix, the stateless package manager, and Docker, the tool that lets you run all of your apps in light-weight containers on a host.

Nix may be a great tool, and help you avoid the possibility of moving parts in your builds, but there are still a lot of edges to smooth out, just simple stuff to make it easier to figure out what's going on and build things.

Installation

Installation was very easy! There are 2 choices - install an entire operating system, or install just the package manager. You can't really deploy the operating system to anything besides AWS, so I chose the package manager.

You install it with

bash <(curl https://nixos.org/nix/install)

No wgetting sources, configuring installation directories, "Permission Denied" errors, it just works and this is one of the main reasons I like this format even if everyone yells all the time that it's a security risk. It is, but there are no better ways to install things at the command line, currently.

Trying it out

Here was where things started to go wrong. The obvious name of the command for a tool named nix is nix, right?

$ nix
zsh: command not found: nix

$ find /  -name nix -executable -type f
No matches found

Okay, this is annoying, back into the docs to see what actually got installed onto my system. From the install page, there's a link to read more about Nix, but no link to a quickstart, or "Try it out", or anything like that. I click "Help" and get this sentence:

This makes me think I am going to need to parse a PDF to find the information I need.

The manual

I open the very large Nix manual. Missed the section that said "Quick Start" while scanning the Table of Contents, maybe because it came before the chapter on "Installation". Instead I start reading "Basic package management". The command I am looking for is nix-env and finally there is something I can type into a shell and run, I'm not quite sure what this does, but this way I can at least verify that it was installed properly:

However, I don't get the same list of packages.

[nix@gazelle ~]$ nix-env -qaf nixpkgs-version '*'
error: getting information about `/home/nix/nixpkgs-version': No such file or directory

This is frustrating, and the note ("nixpkgs-version is where you've unpacked the release") is not very helpful, as nix handled the installation for me, and I don't know where the release is unpacked.

At this point I abandon the manual and Google around for anyone who's tried installing Nix. I find a nice tutorial explaining how to install Nix, search for packages and install them. Problem solved, and a good reminder that documentation should be designed for people that don't read.

Note, my DigitalOcean box with 512MB of memory was not enough to run Nix; I got a "error: unable to fork: Cannot allocate memory" when I tried starting the program, and had to add a 256MB swapfile.

Seeing what else I can do

Normally when I download a new tool I'll pull up the help menu to see all of the things that are possible with the command. For example, if you type python -h, you get:

usage: python [option] ... [-c cmd | -m mod | file | -] [arg] ...
Options and arguments (and corresponding environment variables):
-B     : don't write .py[co] files on import; also PYTHONDONTWRITEBYTECODE=x
-c cmd : program passed in as string (terminates option list)
-d     : debug output from parser; also PYTHONDEBUG=x
-E     : ignore PYTHON* environment variables (such as PYTHONPATH)
-h     : print this help message and exit (also --help)
-i     : inspect interactively after running script; forces a prompt even
         if stdin does not appear to be a terminal; also PYTHONINSPECT=x

Nix doesn't provide anything for "-h", and typing "--help" pulls up the man page, which has the information I want but is pretty heavy weight. Also, with a new user running Bash, the man page came up without the ANSI escape sequences getting escaped. Haven't figured out whether this is my problem or Nix's.

The existence of an extraordinarily large footgun

One time I typed nix-env --install and hit Enter without specifying a package. Nix was a second away from trying to install literally every single package it has, over 5000 of them. This seems like something that no one would want to do, yet it's currently extremely easy to do by accident.

The most frustrating problem of the day

Soon after this, lots of network operations began failing with the cryptic error message 20: unable to get local issuer certificate. The answers on StackOverflow and curl.haxx.se suggest that this is due to a certificate not being there. I was very confused, because there was a certificate in /etc/ssl/certs, other SSL operations were working just fine, and the debug output from curl at the command line indicated it was using the certificate bundle.

It finally took an strace command to see that the network requests were not actually looking in /etc/ssl/certs for the certificate, but somewhere deep in the /nix directory. Setting GIT_SSL_CAINFO=/etc/ssl/certs/ca-bundle.crt in the environment fixed the issue. Once I figured this out, I found people complaining about this problem all over the place.

This means the default installation of git and curl will certainly break git clone for everyone, and really should ship with certificates, or at least a warning when you download the package that you need to get an up-to-date certificate store from somewhere.

Conclusion

There is a stateless package manager, and it can download packages and all of their dependencies. That's really cool, but for the moment there are quite a few usability problems that make this really hard for people to get started with.

Liked what you read? I am available for hire.

Levelers

Posted on

I read a great blog post in college, and sadly I can't find it now, so I'll summarize. It showed a picture of Hearst Castle, and a photo of an average middle-class home, and the text of the post went something like:

  • One of these can travel across the country in 6 hours.

  • One of these can communicate with friends and family on the other side of the country instantaneously.

  • One of these can receive news from the other side of the globe instantaneously.

  • One of these can watch movies in full color and sound in their own home.

  • One of these can expect to live to age 80, and give birth to a child without serious risk of complications.

  • One of these can wash an entire day's worth of dishes in 40 minutes with no human effort.

Hearst Castle. Photo credit Beedie Savage. Creative Commons BY-NC 2.0

The point is, even though Hearst was one of the richest men on the planet, in many ways the average middle class person today enjoys a better quality of life, due to advancements in technology and medical science since the 1940's.

It's really exciting when technologies (air travel, the Internet, smartphones, appliances) become accessible and cheap enough that everyone can enjoy them. But it's even more exciting when the high end of the market comes within reach of most people.

Let's say Bill Gates wants a better smartphone - say, with a longer battery, or with a UI that does exactly what he wants. He's basically out of luck - he can't throw enough money at the problem to get a better phone than what's currently on the market. A phone you can afford is the best one that Bill Gates can buy. I call products like these levelers, because they level the playing field for everyone. It's easy to think of other examples - most software/apps/websites, beers, movies, and more.

So I got excited yesterday when I read about a product that might level the playing field for another experience that's currently only for rich people.

To get a sense of what JauntVR has built, their technology is described as “an end-to-end solution for creating cinematic VR experiences.” Their camera films real world footage from everything surrounding it, and their software stitches those clips together to create a seamless experience. The wrap-around film capture means that you’re able to swivel in any direction to maintain that feeling of “actually being there.”

Rarely is the window into the future as stunningly clear as was for me for the next few minutes inside that Oculus Rift. So what was it like inside? (Keep in mind: writing about the mindshock of live action VR, is quite like trying to share a photograph of your favorite song. Words simply cannot do justice.)

I settled into a swivel chair at the center of a dark surround-sound equipped room, slid on the Rift, and instantly I was no longer in Palo Alto but sitting inches away from a string quartet performing inside a luxurious concert hall. Stunned by the realism (it is real after all!) I began turning in every direction, to discover that behind me I could see the full venue where an audience would sit. Then I understood where I was – right where the conductor would stand. Not a bad seat and with the surround sound so clear, I felt as if I was actually there.

Just like that - millions of people can suddenly all sit courtside for the NBA Finals, or even hover above the court, and suddenly, my view of the game isn't from section 400, it's as good as Jack Nicholson's.

This got me really excited for the future of virtual reality, and the new things that people are going to build on top of it. I can't wait to see what people build.

Liked what you read? I am available for hire.

Storing Photos for the Long Term

Posted on

You have photos on your computer. You would probably be really sad if you lost them. Let's discuss some strategies for ensuring that doesn't happen.

What you are doing now is probably not enough.

Your current strategy is to have photos and critical files stored on your most current laptop and maybe some things in Dropbox. This means you will probably lose your data sometime in the next three years.

Hard drives fail, often, and are unrecoverable, or expensive to recover.

The software that manages your photos is written by people who are bad at their jobs, or didn't anticipate the software running on (insert hardware/software condition 10 years from now here) and it breaks, destroying your photos in the process.

Backup services fail, often enough to make you worry. Apple can't be trusted to reliably deliver messages with iMessage, I don't trust Time Machine at all.

Apartments and cars get broken into and laptops/external drives are good candidates for theft. You can buy renters insurance, but you can't get your photos back.

What you should do

I'm going to focus specifically on keeping photos for a long time. For files and folders which change more often, I use git and source code tools like Github or Bitbucket. For work environments that take a while to set up, I try to automate installation with shell scripts instead of trying to store the entire environment via Time Machine or similar.

I'm also going to pick a thirty year time horizon, just for fun. If you want something to last for thirty years, you can't just store it on your local machine because your hard drive will probably fail between now and then, and then you lose your photos. So you want to store it on your machine and then also somewhere offsite (e.g. not in the same 5-mile radius as your machine).

Storage Tool

Which raises the question, which storage/backup companies will be around in 30 years? Any small enough candidate, even Dropbox, could get acquired or shut down in that time frame. My guess right now is that Amazon Web Services will be around the longest, because it is profitable, already part of a large, growing company, and the service is growing rapidly.

Specifically, I am putting a bet on Amazon Glacier, which has extremely low storage costs - $0.01 per GB - and is one of the most reliable services Amazon runs. Glacier is a subset of Simple Storage Service (S3) which has had extraordinarily good availability in the 7-8 years it's been available. In addition Amazon regularly publishes information on the technology underpinning S3, see "Amazon Dynamo paper" for example.

I use Arq to back up photos to Glacier. It seems fairly stable, has software preferences for the right things, and I am encouraged that the author charges for the software, which means he/she has an incentive to continue developing the product and making sure that it works. This is $30 but this is still much, much cheaper than any other tool (iCloud for example would be $100 per year).

I have 52 GB of files, which means I'll pay roughly $7 per year to have 11 years of photos stored safely in the cloud. Not bad.

I would consider Tarsnap as well, which encrypts your data, but it's currently 2.5x the price of Glacier. I expect this price to decline soon.

Photo Management Software

The second piece is you need to choose a stable piece of software for viewing and managing your photos. This is orders of magnitude more risky than Glacier. The ideal piece of software would have:

  • An easy to understand file format, published online

  • Source code available online

  • Some support for grouping photos into albums and importing them from my phone/camera/whatever

  • Some sort of tool for auto-adjusting the layers on a photo, cropping it, editing the brightness/contrast. Not Lightroom, but enough to make a photo better than it was.

  • Supports hundreds of gigabytes of photos without falling over.

I haven't done as much research into this as with backup solutions, but there are a few tools. Picasa is supported by Google and relies on Google's charity to stay running and supported. Lightroom is very nice, but overshoots my needs, is very expensive, and Adobe may run out of money and fold within the next 30 years. This leaves iPhoto, which isn't well documented, or open source, but mostly works, some of the time, can crop/edit photos while saving the originals, and is a core component of Apple's Mac product, which may also die, when we all have tablets. At least iPhoto stores the files on disk.

If I was a better person, I'd manually arrange photos in files on my filesystem and use that. But I am not.

Problems

In this game it's a question of how paranoid you want to be, and how much your photos are worth to you. If they're worth a lot it's worth investing significant time and resources into redundant backup systems. Specifically, the 3-2-1 rule suggests storing backups in 3 different places, 2 different file systems (or photo management tools), with at least one offsite. For photos, backing up to CD's or tapes is not a terrible option though it's not very efficient and CD's also die. Using a 2nd photo management software solution, storing the data for that one on an external drive, and backing one of them up to Glacier every night is not a terrible idea.

My photos are worth a lot to me, but I'm not going to go insanely overboard; if my hard drive dies, and Glacier loses my data, that would suck, but I'm willing to gamble on the one-in-a-million odds of them not both happening simultaneously.

I am most worried about the management software; recently iPhoto decided I had no photos in my library and deleted all of the metadata for those photos (albums, rotation information, etc), leaving only the raw copies in my library. This was very sad, though I didn't lose the photos themselves, and might be able to recover the metadata if I am lucky. So yeah, I am not too happy with this. I now store important iPhoto databases in git, backed up to Bitbucket, so I can pull them back down in the event of another catastrophic failure.

Conclusion

This is too long already. Ensuring your photos aren't lost is difficult, and probably requires professional experience as a computer programmer to get right, or for you to part with a significant amount of money, or achieve a large amount of good luck, to avoid the bad things that happen to most people who just hope their photos stick around. I wish you the best of luck.

Liked what you read? I am available for hire.