Speed up trace mode (GSoC Project)

[Mihir Luthra]

Hi Clemens,

I had some points in mind about mapping more memory when we run out of
memory, which I wanted to discuss with you.

Also you are right, this project is not at all short. I realise now, many
conditions need to be taken care of while doing tasks.

Each process shared 2 types of memory. One which is for the path checking
data structure.


And other shared memory which is mapped for read and write before the other
shared memory is for these:

bool isExpanding; —— (i)
int memoryAvailable; ————(ii)

pid_t expanderPid;                  (iii)
pthread_id_np_t expanderTid;    (iv)

    //(iii) and (iv) variables are only required for Approach A.

bool isReading ————(v)
pid_t readerPid;-------- (vi)
pthread_id_np_t readerTid;————(vii)


The memoryAvailable(ii) variable here is used to specify the size of the
cache data struct memory.



*Approach A:*

There are many conditions which need to be taken care of while expanding
the shared memory knowing other threads and processes may also access the
same memory for read or write.

The shared memory which is constructed of Ctrie(including an offset
variable in it to get location of next node), gets accessed for:
1) Read
    By the processes who are checking this memory if they find path here
and don’t need to make server connection.
    This type of process would open mapped region for read
    And in other memory they set readerTid and readerPid by compare and
swap and also sets isReading to true.
    While done reading, when the thread tries to reset these readerTid and
readerPid by CAS, if the old value is found the same as expected, the
isReading is set to false. (This ensures, isReading is only true if any of
the process is reading)

2) Write
      This type of process didn’t find the desired path in the shared
memory, which is why had to make a socket connection.
      a) Whoever made a server connection and checked a new path would try
to insert that new path in the shared memory.
      b) Also, this type of process before sending path data to server for
check should also check if the amount of shared memory left is less than a
certain limit because there is a high chance that if a server connection is
being made, the newly checked path may want to get written to the shared
memory and at that time the shared memory shouldn’t lack in space. So
before the path data is sent, more shared memory is mapped.

Now one or more process may be under the same condition, all wanting to map
more memory.
So here,  the region responsible for mapping more memory is our critical
section which needs to be ensured that is getting accessed only by a single
thread.

The entry section of critical section would comprise of 3 variables.
expanderPid, expanderTid and isExpanding. (These are created temporarily in
the respective processes first).
This entry section is very much similar to dekker’s solution of critical
section. where isExpanding acts like a turn variable and expanderTid and
expanderPid act as flag for a particular process.
Now before entering the critical section for mapping memory, the same three
variables at the beginning of the shared memory are compared and swapped
atomically (the atomic CAS is already implemented in file map function).
The process try to swap from the shared memory and even once of the old
value doesn’t match with new value, the particular process stops the
attempt to map more memory because the old value won’t match for a sole
reason that some other process was ahead of this one if taking lead towards
critical section. The tid and pid variables at the start ensure that the
process is being expanded by the right thread.

When the isExpanding is changed, trying to read also stop right there and
enter a loop until isExpanding is set back to false.
Now whichever thread enters critical section, creates a new file, maps
memory, and

Now this process if made to map more memory first sets isExpanding(i) true.
The isExpanding variable is for processes reading from memory, so that they
start looping until this value is set to false.
Then the process has to create a new file with mkstemp again, map more
shared memory (all tasks of mapping more memory done here) and then it
checks continuously the isReading variable of shared memory, and whenever
it is found false, it changes memoryAvailable(ii) accordingly.
This memoryAvailable is checked by processes each time they are using the
memory, so that if this changes they map newly available memory correctly.
This ensures memory management in a lock free manner.
But the only downside here is that the thread responsible for creating all
this memory isn’t under our control, it might die any moment.
Now this can be taken care by some more variables informing other processes
that they need to continue this mapping memory instead.
But a better approach should be the next one-

*Approach B:*

The process responsible for mapping the memory can be made by us.
We don’t have any control on the processes that our library is injected to
but we have full control on the process we create.

The process we create can share memory with those processes and detect if
the limit where we need to map more memory has reached.
This process now maps more memory ( no need of iii and iv here because no
other process can do this anyway)
and in a similar fashion as above gets new memory mapped into other
processes as well.

******Approaches end here

Also, its best to predict the memory so that situation of allocating more
memory arises the least number of times.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.macports.org/pipermail/macports-dev/attachments/20190404/22fb2cbf/attachment-0001.html>