Speed up trace mode Project GSoC

[Clemens Lang]

Hi,

On Wed, Mar 20, 2019 at 09:06:11PM +0530, Mihir Luthra wrote:
> I am not a master in dealing with low-level system stuff, but as I
> have worked pretty much with unix shell scripting and C language, I
> can connect to points.
> 
> I wanted a few tips from you regarding the project:
>      1) What way should I proceed?
>          Should I start with understanding the trace code?
>          If yes, then can you give me a some idea on which files I
>          have to work with and in what order should I start
>          understanding them?

That's definitely required for this task, yes. The most relevant parts
are the client-side in src/darwintracelib1.0, most notably darwintrace.c
[1]. Check __darwintrace_setup() and __darwintrace_get_filemap() (most
notably the use of compare-and-swap in that function) and
dependency_check(). You should understand why the compare-and-swap in
__darwintrace_get_filemap() is required and look at the different
scenarios that can happen when two threads call this function at the
same time. The same principle of non-blocking synchronization using
compare-and-swap would need to be applied for this project.

Server-side, look at pextlib1.0/tracelib.c [2]. The main server is
handled in TracelibRunCmd which accepts new connections and processes
pending requests using kqueue(2)/kevent(2) to ensure non-blocking
processing. dep_check() does the query of the registry using SQLite.

Additionally, port1.0/porttrace.tcl is the somewhat higher-level setup
of the tracelib.c server component from Tcl which eventually calls
'tracelib run' in a separate thread to start the C code.

>      2) Are there any books or papers or anything which I can refer
>      to?

I'm not in a position to recommend current papers on this, but a good
starting point might be research on lock-free map-like data structures,
e.g. a Ctrie [4] or related data structures [5].

>      3) Shall I continue contacting you on mail or should I use some
>      other way?

The usual way is sending me an email but Cc'ing the macports-dev list,
so that others can also contribute. I've added the list to Cc now.


> *******************************************************************************************************************
> A short Report on what I understood and worked upon
> *******************************************************************************************************************
> 
> [...]
>
> I got some high level understanding on the way code is working
> 
> 1)That DYLD_INSERT_LIBRARIES dynamically links the tracelib during build so
> that all file related operations are under our control.
> 2)Now during run time( most probably the desertroot phase) when check is
> being made , in the 3rd possibility, as data is always being fetched
> from server and not cached, we need to implement an efficient way for
> cache storage which as u told by mmap(2) and forming a shared memory
> for all processes and it is spoc for server interaction. Some data
> structure needs to be implemented to reach to all processes fast. but
> we can’t point to the this shared memory as we only get offset info
> from mmap 2. (This point maybe a bit ambiguous I need to research more
> to understand this completely)

This does not only apply to the destroot phase - we need to limit file
accesses during both the configure and build phases, too, so that the
build systems to not inadvertently find things on the filesystem they
shouldn't see.

As for the offset portion, the problem is as follows:

 - You mmap() a file descriptor into memory (where that file descriptor
   comes from remains to be seen, but it can also just be a file on disk
   for all intents and purposes for now). That file descriptor will
   point to the same file in all processes.
 - We do not control the memory layout of the processes our library is
   injected into – hence we cannot assume a fixed address for our cache
   data structure, but must let mmap(2) pick a free address. This means
   that different processes will have the same cache data structure at
   different addresses.
 - Pointers only work if all processes map the chunk of memory at the
   same address. Hence, we can not use pointers in our data structure,
   but instead we can use offsets from the beginning of our shared
   memory block.
 - What was previously *pointer now becomes *(base_address + offset).
   The code that deals with the cache data structure needs to be aware
   of that.


> On Wed, Mar 20, 2019 at 3:04 AM Clemens Lang <cal at macports.org> wrote:
> 
> > Hi,
> >
> > On Sun, Mar 17, 2019 at 01:03:00PM +0530, Mihir Luthra wrote:
> > > I wanted to contact you regarding the “Speed Up trace mode”
> > > project. I gave a quick read to the documentation to get the basic
> > > understanding of MacPorts.
> > >
> > > I am giving a small description on what I understood,
> > >
> > > Basically, user may have installed packages or files in past which
> > > reside in certain locations.(e.g. /usr/local) Now when MacPorts is
> > > installing a new package, the name of files may conflict with
> > > those pre installed(by the user) and create unpredictable
> > > dependencies unnecessarily increasing build time or errors. The
> > > function of trace mode is to scan all locations that the package
> > > to be installed will access and hide files which are not needed.
> > > But enabling trace mode makes the build process really long. So
> > > what we have to do is optimise the trace mode library by using
> > > better data structures or improvising it.
> >
> > That's mostly correct. On the techical details, the scanning of the
> > files that are being access happens during the build. We inject a
> > library into the processes started during compilation that overrides
> > all libc functions that deal with files (e.g., open(2), stat(2),
> > readdir(3), etc.) and then decide at runtime whether a file should
> > be shown or hidden. If it should be shown, we call the normal
> > implementation of the function, if it should be hidden we return an
> > error code and set errno. The method we use to inject our code into
> > the build is called DYLD_INSERT_LIBRARIES. On Linux, the same
> > technique is called LD_PRELOAD (which may be easier to google).
> > There are subtle differences between Linux and macOS here, but they
> > don't matter for now.
> >
> > The workflow to check whether a file is shown or hidden is as
> > follows:
> >
> > 1. When the first file is checked, the library connects to a unix
> > socket and obtains a list of access rules.
> > 2. The path of the file is checked against the access rules. This
> > can lead to three results:
> >
> >  a) Access is granted. We do this for files in /usr/include, for
> >  example, since we don't want to hide them.
> >  b) Access is denied. We do this for paths that should never affect
> >  our build, e.g. /usr/local.
> >  c) The path is sent via the unix socket to our server component,
> >  which checks the SQLite database of installed files and ports (the
> >  so-called "registry") to find out which port provides the file. It
> >  then checks whether the port that provides the file is a dependency
> >  of the current build. It sends this information back to the
> >  injected library via the socket, which then decides to allow or
> >  deny access.
> >
> > This last part is what's slow and could benefit from optimization.
> > Note that we do not do any caching of this data, e.g. if a process
> > opens a file in the 2c category 20 times, we ask the server 20 times
> > to do the lookup. Additionally, each new process that gets spawned
> > needs to check for the same files again, because there is no shared
> > data between those processes.
> >
> > In my mind, a good idea to optimize trace mode would be to mmap(2) a
> > piece of shared memory into each of the processes our library gets
> > injected to and build a fast path-to-allow/deny data structure in
> > this shared memory area so that the 2c-type query would only have to
> > be sent to the server once for the entire build and would otherwise
> > be cached.
> >
> > The problem here is that we do not know where in the address space
> > of a process this piece of memory would be, so we cannot simply use
> > pointers but would have to use offsets from the start of the memory
> > region. Additionally, we need to think on how to grow the memory
> > region if it runs out of space (while keeping in mind that multiple
> > processes might attempt to do so at the same time). Also, because we
> > do not know in which state and configuration the processes into
> > which our library gets injected are, we must assume that using locks
> > (e.g. mutexes) may end up causing a deadlock and fail the build.
> > Consequently, this shared data structure must use lock-free
> > primitives, such as compare-and-swap.
> >
> > There may be already implementations of such a data structure out
> > there that we could re-use (or there may be implementations that
> > could be turned into such a data structure with relative ease, e.g.
> > if they are already lock-free but use pointers rather than offsets,
> > we may be able to modify them to use offsets).
> >
> > Note that this projects requires a fair bit of low-level system
> > knowledge.
> >
> > If you have any further questions, feel free to ask.

[1] https://github.com/macports/macports-base/blob/master/src/darwintracelib1.0/darwintrace.c
[2] https://github.com/macports/macports-base/blob/master/src/pextlib1.0/tracelib.c
[3] https://github.com/macports/macports-base/blob/master/src/port1.0/porttrace.tcl
[4] https://en.wikipedia.org/wiki/Ctrie
[5] https://arxiv.org/abs/1709.06056?context=cs

HTH,
Clemens