Implement user symbol translation for BPFd

[jcanseco]

This depends on PR #25.

[joelagnel]

I don't see the point of the extra SymbolResolver class really. The centralization argument is too weak to warrant creation of a new C++ source file with additional caching logic, and the cache creation can be done only once per-pid from bpfd.c itself, instead of creating it every time on every lookup command.

[jcanseco]

Hey, so I wasn't 100% sure if the SymbolResolver class was the way to go, which is why I added it as a separate commit for now, so that I can easily reverse it if you did not think it was a good idea.

The issue of having an extra commit aside though, how can we do the caching of the ProcSyms instances just from bpfd.c? I basically introduced SymbolResolver so we can take advantage of C++'s std::unordered_map as a nice way to cache ProcSyms for each pid (so that we don't recreate it for every sym lookup for each pid), but I'm kind of confused how we can efficiently replicate this functionality from just C in bpfd.c alone since C doesn't really come with any nice data structures aside from, well, arrays. Am I just missing something here?

[joelagnel]

Just create an array of PID->pointers

[jcanseco]

Okay, so what kind of implementation are looking at here?

I'm assuming we're thinking of something like this:

We're gonna use an array as our main data structure for holding references to the ProcSyms instances.

The array itself can be an array of usym structs, where a usym struct can be defined as:

struct usym {
    int pid;
    void *usym_cache;
}

This way we can retrieve the ProcSyms instance that belongs to a given PID. We can also find out for which PIDs we've previously created a ProcSyms instance for.

The problem I see with this though is how do we handle the case where the array becomes filled to capacity, and we have to create another ProcSyms instance? I understand we can just create a new array and copy all the elements over, but this'll be just somewhat of a re-implementation of std::vector.

Also, PID lookup in this case would be O(n) since we would have to traverse the whole array in the worst-case scenario to find the particular PID we're looking for, as opposed to std::unordered_map's O(1) lookup. Wouldn't this hamper performance since some BCC tools perform a lot of symbol lookups?

I'm still somewhat of a beginner at C and my background is mostly OOP, so please forgive me if this is actually just an obvious problem.

[joelagnel]

You can index the array with the PID which makes look up O(1). 32768 is typically maximum pids in Linux, but if a rare collision occurs (say max pids run out or a pid is reused), then a collision can be detected easily by storing the full name of the exe along with the PID in the array. To handle the case of number of PIDS > 32k, which isn't the default - you can easily just store the full PID and the full EXE name and detect collisions. Incase of collisions, just return "unknown". I'd say worry about these cases later though and for now just do a plain PID->ProcSyms(or whatever ptr) array mapping.

[joelagnel]

You're not handling collisions or the special cases in your earlier PR anyway by the way...

On Fri, Mar 9, 2018 at 11:35 AM, Jazel Canseco notifications@github.com wrote:

Hey, so I wasn't 100% sure if the SymbolResolver class was the way to go, which is why I added it as a separate commit for now, so that I can easily reverse it if you did not think it was a good idea.

The issue of having an extra commit aside though, how can we do the caching of the ProcSyms instances just from bpfd.c? I basically introduced SymbolResolver so we can take advantage of the C++'s std::unordered_map as a nice way to cache ProcSyms for each pid (so that we don't recreate it for every sym lookup for each pid), but I'm kind of confused how we can efficiently replicate this functionality from just C in bpfd.c alone. Am I just missing something here?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/joelagnel/bpfd/pull/26#issuecomment-371922806, or mute the thread https://github.com/notifications/unsubscribe-auth/AACSVA7dlGkKEm5UjXX__-tbDdxNpIA1ks5tctmFgaJpZM4Sjk5u .

[jcanseco]

Ah okay that explains it then. I didn't know there was a max cap for PIDs in Linux. I'll deal with this problem in a bit then.

[joelagnel]

Default is 32k, so that's why I mentioned to handle collisions. If a collision occurs, its just fair to make the request fail for now.

So the array should look like: Array[PID % 32k] = struct { FULL-PID, POINTER-TO-ProcSyms }

Compare FULL-PID on a look up and make sure, its the same as expected. If its different, then there's a collision and make the look up fail. Add some useful messages that a collision occurred.

[jcanseco]

For the collisions scenario, isn't it enough to just return a failure if the given PID goes over the 32k default cap? (i.e. no need to check if a ProcSyms already exists at the index PID % 32k, but just do a simple PID > 32k check)

For the other type of collision (where the PID is reused for a different process), wouldn't it be better to just overwrite the existing ProcSyms we cached before for that PID? After all, the PID->ProcSyms mapping held at that index is now outdated. Also, this seems better to me since then we can still return a successful lookup instead of just outright failing the request. Currently thinking about how to implement this, but didn't get to it yet, however. It's also worth nothing that BCC does not handle this collision case either for some reason.

[jcanseco]

Also please see the most recent change I made. I'll squash it later into the first commit; I just want to bring your attention to the changes I made related to caching ProcSyms to see if it's suitable.

Naturally, I already made sure to test it.

[jcanseco]

Added another commit that checks for the PID going over the default max of 32k. I also plan to squash this with the first commit ("Implement user symbol translation for BPFd")

[joelagnel]

No. If PIDs are > 32k and nothing less than 32k was cached, then it should be cached since there's nothing to collide with. In other words its normal and not an error.

[jcanseco]

Okay, how about this one (see most recent commit).

It caches the ProcSyms instance, and handles both collision cases (pid reuse and pid wrap-around due to 32k cap).

Let me know what you think. If you think it's good, I'll squash the commits and propagate the change onto the BCC PR.

[jcanseco]

Made the requested changes. PTAL.