Speed up trace mode Project GSoC

Tue Mar 26 07:52:14 UTC 2019

Hi,

Thanks for the helpful response ^_^.

I have been through the code files of porttrace.tcl, tracelib &
darwintrace. I understood their high level working.
I will go through the function __darwintrace_get_filemap() to understand
more about compare & swap & will look for more lock free primitives. ^_^.

Regards,
Mihir

On Tue, Mar 26, 2019 at 1:19 AM Clemens Lang <cal at macports.org> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.macports.org/pipermail/macports-dev/attachments/20190326/e785f358/attachment-0001.html>