in Hacker School

Hacker School Day 40 – Making pstree Faster/Ugly – No Regex

This is a continuation of the first post, Hacker School Day 40 – Making pstree Faster/Ugly.

The first change was to replace my use of a regex to parse the /proc/$pid/stat file. The file looks like this, with what I need in bold:

29783 (cat) R 2681 29783 2681 34818 29783 4194304 228 0 0 0 0 0 0 0 20 0 1 0 1349984439 3383296 63 18446744073709551615 134512640 134559492 4291213280 4291212792 4151335790 0 0 0 0 0 0 0 17 0 0 0 0 0 0 134565616 134566236 136880128 4291216343 4291216363 4291216363 4291219439 0

For me, I’m interested in the name of the program, which is in parenthesis, and the 4th field, which is the ID of the parent process. You can run man proc to see what the other fields mean.

A simple whitespace-delimited split won’t work, because a process can have whitespace in its name. I do this in my Zulip-IRC transport by renaming its children to be be “zulip-irc-ii reader” and “zulip-irc-ii writer”.

The process name can also have a parenthesis in it, which is also terrible:

? ~ perl -E '$0="why))))"; sleep 100' & pgrep -l why
[1] 30120
30120 why))))

So I wrote a regex to capture the information in the parenthesis, and the 4th field. My first profile run showed a lot of regex noise, so this was the first place to start chopping.

String Functions

I replaced the regex with some string functions to get the process name and parent PID. I got the index of the first parenthesis, and the index of the last parenthesis, and then returning the string within that range for the process name. To get the parent PID, I took the line, starting from the last parenthesis, and split on whitespace. I took the 2nd field, which was the PPID.

This was a pretty significant improvement! Also, using the right tool counts — I was originally using bytes.Index, which takes a byte array of separators. Since I just needed the index of an individual character, bytes.IndexByte was the better choice. It only takes one byte to search for, and for Go, it’s implemented in assembly.

But I felt bad splitting the string to get the parent PID. Go’s bytes.Fields method (which is what I was using) returns a list of every field, and I only needed one field.

29783 (cat) R 2681 

So, after the last parenthesis of the string (after the process name), there’s a space, then a single uppercase letter (representing the state of the process), then another space, then the parent process ID. Adding three to the index of the last parenthesis gets the first character of the PPID, and you can capture up until the next space. This was much faster than using the Fields method.

Going too far

I use LastIndex to get the last parenthesis for the process name. It’s just a for-loop that scans backwards. Since process names can have a parenthesis in them, I need to do a last index, but I don’t need to pass the whole string from /proc/$pid/stat. If I knew how long a process name could be, I could pass a small slice of the string up to the possible length to make the for-loop shorter. This is kind of ridiculous but I figured it’d be fun to find.

Let’s dive into the Linux kernel to find out how long the process name in /proc/pid/stat is:

  1. The /proc/pid/stat file contents get printed here: fs/proc/array.c#L470
  2. tcomm is the variable representing the process name. It is populated by get_task_comm here: fs/proc/array.c#L404
  3.  get_task_comm strcopys from task_struct‘s comm element: fs/exec.c#L1030
  4. task_struct‘s comm element is defined here as a character array with TASK_COMM_LENGTH characters: include/linux/sched.h#L1396
  5. TASK_COMM_LENGTH is defined here as 16: include/linux/sched.h#L268

So a process name can be 16 characters. It’s a fun dive, but it’s way easier to prove by just making a long name and counting where it stops:

? pstree git:(master) ? perl -E '$0="0123456789"x10; sleep 100' & pgrep -l 0123
[1] 30670
30670 012345678901234

There’s 15 characters there, plus the null terminator for the string = 16 characters.

So I searched for the last paren in the string consisting of the characters from the first parenthesis to 16 characters ahead.

The next change was changing how files were read. It’s just as wonky as this, so stay tuned.

Write a Comment

Comment