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 <[email protected]> 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 <[email protected]> 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 >
