Hello LKL Community,
I was looking through the issues section of the LKL github repo and could
find this issue 370 which talks about SMP Support in LKL.
https://github.com/lkl/linux/issues/370
The project prototype linked to the above issue does not currently build on
Ubuntu 20.04(not sure if we need a specific os to get the build working),
but the threads suggest that it used to pass certain basic tests. Apart
from a few arch(x86,arm64) dependent duplicated code (which were suggested
to be replaced with gcc builtins), can this be a good way to move forward
with the project?
Based on some of the code I read from the SMP prototype, the most
useful part is, on every lkl_syscall(...) call, it tries to acquire a lock
with the currently executing cpu, smp_processor_id(...), and once it
acquires a lock, it checks if the executing thread is a host thread, if not
it makes it one using the new_host_task(...) call. This could to some
extent solve the problem I'm currently facing with deadlocks on the cpu
mutex, after a switch to a non host thread which never had any locks, and
there already exists a host thread which owns the lock over a blocking
operation.
A few questions that I had :
- How feasible would such a solution be given the DCE environment ?
- Which parts of the kernel should be taken most care of while
implementing such an architecture, for ex IRQs, locks, etc. ?
- DCE works based on a fiber scheduler, i.e, unlike normal system
threads which are scheduled by the host kernel, it creates its own fiber
contexts and switches back and forth using a scheduler and yields to other
fibers when a particular task has to be executed. How would we ensure that
every fiber that's currently running, would eventually get a lock ? I'm
actually trying to consider a hypothetical situation, where there are 4
cpus on the machine, and we serially schedule 4 jobs which ultimately issue
blocking network calls and they all keep holding a cpu lock over their
current executing cpus until they return, how would we avoid such
situations? But, maybe this scenario would never arise, because in
practical network simulation, every server must rely on a client present
within a given network, so there should exist a simulation application that
would send the desired data to the server, ultimately returning from an
accept call, and dropping the lock using lkl_cpu_put(...) .
- The CONFIG_NR_CPUS flag is set through the Kconfig. How huge could
this value go up to, because a really high value might assure that we can
have more number of blocking operations at the same time ?
- Does the NR_CPUS flag have any impact on the smp_processor_id(..), as
in dynamically moving over to the next available virtual cpu?
- Can there be a workaround to acquire multiple unique cpu locks,
without implementing an actual SMP architecture ? Naively : We could
create an array of cpu locks, and for every syscall keep allocating them to
a calling thread, and make it a host thread. Though this algorithm would
have O(n) time complexity, it could be brought down to O(log n) with a
divide and conquer approach, with a linear space complexity. But doing so,
we might have to take care of the syscall IRQs.
- What more should we consider apart from the above stated points ?
Note : The DCE host applications are exposed with an API which can have
access only to system calls (socket,listen,bind,accept,sendmsg,....), so
deadlocks which could arise (as said by a user in this comment
https://github.com/lkl/linux/issues/370#issuecomment-503128409 ;), could be
avoided.
I would be really grateful if the community could help me with any
suggestions on how to proceed further.
Thank You,
Parth Pratim Chatterjee
On Wed, 2 Jun 2021 at 12:21, Parth Pratim Chatterjee <
parth27official@xxxxxxxxx> wrote:
Hello,On Wed, 2 Jun 2021 at 12:21, Parth Pratim Chatterjee <
Sorry for the late reply. I've been setting up the public repos as I had
been working on a local branch.
LKL Repo : https://github.com/ParthPratim/linux/tree/dce-b2
DCE Repo : https://github.com/ParthPratim/ns-3-dce/tree/lkl-dce
Bake Repo : https://gitlab.com/ParthPratim1/bake/-/tree/lkl-dce
To build my project on Ubuntu-20.04, please follow the following steps :
git clone https://gitlab.com/ParthPratim1/bake.git
cd bake
git checkout lkl-dce
python3 bake.py configure -e dce-linux-dev
python3 bake.py download
python3 bake.py build
cd source/ns-3-dce
sudo python3 waf --run dce-linux-simple (sudo is required for getting
access to /dev/net/tun interface for netdevice setup)
To get a much better understanding of where the program currently is stuck
at :
sudo NS_LOG="DceKernelSocketFdFactory=level_all" python3 waf --run
dce-linux-simple
Currently only dce-linux-simple was made to load liblkl.so, but other
examples can be enabled in the same way.
Under the bake/source you can find the folders : lkl and ns-3-dce, the
source can be tracked here.
Please let me know if you have any issues setting it up.
Thank You,
Parth Pratim Chatterjee
On Mon, 31 May 2021 at 20:17, Matt <mattator@xxxxxxxxx> wrote:
Hi,
Great project !
Do you have any public branch where we can track your progress and
eventually comment on (dont care if it's "dirty"): it would make it
easir to build/reproduce & help you.
Cheers,
Matthieu Coudron
Le lun. 31 mai 2021 à 14:16, Parth Pratim Chatterjee
<parth27official@xxxxxxxxx> a écrit :
integrate LKL with ns-3’s DCE(
Hello LKL Community,
I have started working on a Google Summer of Code project that aims to
https://github.com/direct-code-execution/ns-3-dce) to enable host
simulation scripts to make use of the linux networking stack to make
realistic simulations of complex networks.
Linux kernel version 4.4, but over the years the project hasn’t kept pace
DCE Currently makes use of net-next-nuse-4.4.0 to extend support to
with the newer linux releases and thus I am now working towards bringing in
support for the latest linux kernel releases. LKL interested me because it
currently supports Linux 5.3 which is somewhat close to what I am trying to
achieve (support for latest kernels could be added with little more work).
up all the host operations and important structures like
I had initially come up with a solution to make this integration. I set
lkl_host_ops(threads,mutexes,semaphores,debug, etc.) and mapped LKL
networking syscalls to our socket calls made in DCE. I then loaded the
liblkl.so as a shared library in DCE and then called an initialization
function which maps all the DCE and shared linux library functions to
respective functions for host simulation scripts to run, also sets up the
netdevices and also calls lkl_start_kernel(...). This is an abstract
summary of what I specifically did to integrate LKL.
execute, but on blocking network operations such as accept(...) the
On testing the above, I found that things did build, compile and
applications got stuck. This was because the LKL kernel scheduler was not
scheduling the DCE threads and thus the client applications could not
execute a corresponding connect(...) call, which leads to the server thread
to be sleeping on an infinite timeout on schedule_timeout(..) and
inet_wait_for_connect(...).
kernel scheduler.
To solve the above problem, I tried to make some changes into the LKL
sleep for the given timeout , call the DCE scheduler first to execute the
I did the following things :
For every schedule_timeout, I put the current DCE calling thread to
other DCE threads sleeping in the queue, and call the LKL kernel scheduler.
In inet_wait_for_connect, after we prepare_to_wait_exclusive(...) toput the task in a TASK_INTERRUPTIBLE state, put to sleep the current
calling DCE thread and call the DCE scheduler.
Note : I did not change the schedule(...) function as some init callsin start_kernel(...) required scheduling other workqueue etc., and if we
did switch the task(before start_kernel returns), we would start another
DCE thread that would use the kernel stacks which haven't been initialized
yet.
thread, control switched to the second thread, and a socket(...) LKL
After I did the above changes, after the accept call by the first DCE
syscall was invoked, but this time the lkl_syscall(...) entered a deadlock
on getting the cpu lock on lkl_cpu_get(...)
lock at any particular time (as far as I understood the architecture, do
This was probably because only the host thread could be holding the cpu
correct me if I’m going wrong).
inconsistent and would obviously lead to failures but even if it doesn't
Even if we ran lkl_cpu_change_owner for every syscall, it would be
fail, LKL would guarantee it fails. LKL probably works on the idea that
only one host thread acquires the lock and thus when we manually make the
previous thread drop the lock using lkl_cpu_put, make the current thread as
host using set_thread_flag(TIF_HOST_THREAD) and then change the cpu owner,
the subsequent syscalls would fail as the cpu.count keeps increasing which
has an upper bound of 1.
https://github.com/direct-code-execution/ns-3-dce/blob/master/model/task-manager.cc#L414
A few important points to consider about DCE :
DCE uses Fibres (Light Weight Threads LWP)
DCE Task Scheduler can be found here :
DCE loads the linux kernel as a shared libraryin DCE and mapped through macros. For example : every socket(..) call in a
DCE makes use of libc hijacking, i.e. some libc functions are rewritten
simulation script leads to calling dce_socket(...) which further makes a
lkl_syscall(_NR_socket,..) inside the loaded LKL library.
Would add more details as required to better understand the problemstatement
possible solutions and propose ideas on how we should approach to integrate
It would be great if the LKL community could help me figure out
LKL into DCE.
Thank You,
Parth Pratim Chatterjee
Hello,
Sorry for the late reply. I've been setting up the public repos as I had
been working on a local branch.
LKL Repo : https://github.com/ParthPratim/linux/tree/dce-b2
DCE Repo : https://github.com/ParthPratim/ns-3-dce/tree/lkl-dce
Bake Repo : https://gitlab.com/ParthPratim1/bake/-/tree/lkl-dce
To build my project on Ubuntu-20.04, please follow the following steps :
git clone https://gitlab.com/ParthPratim1/bake.git
cd bake
git checkout lkl-dce
python3 bake.py configure -e dce-linux-dev
python3 bake.py download
python3 bake.py build
cd source/ns-3-dce
sudo python3 waf --run dce-linux-simple (sudo is required for getting
access to /dev/net/tun interface for netdevice setup)
To get a much better understanding of where the program currently is stuck
at :
sudo NS_LOG="DceKernelSocketFdFactory=level_all" python3 waf --run
dce-linux-simple
Currently only dce-linux-simple was made to load liblkl.so, but other
examples can be enabled in the same way.
Under the bake/source you can find the folders : lkl and ns-3-dce, the
source can be tracked here.
Please let me know if you have any issues setting it up.
Thank You,
Parth Pratim Chatterjee
On Mon, 31 May 2021 at 20:17, Matt <mattator@xxxxxxxxx> wrote:
Hi,
Great project !
Do you have any public branch where we can track your progress and
eventually comment on (dont care if it's "dirty"): it would make it
easir to build/reproduce & help you.
Cheers,
Matthieu Coudron
Le lun. 31 mai 2021 à 14:16, Parth Pratim Chatterjee
<parth27official@xxxxxxxxx> a écrit :
integrate LKL with ns-3’s DCE(
Hello LKL Community,
I have started working on a Google Summer of Code project that aims to
https://github.com/direct-code-execution/ns-3-dce) to enable host
simulation scripts to make use of the linux networking stack to make
realistic simulations of complex networks.
Linux kernel version 4.4, but over the years the project hasn’t kept pace
DCE Currently makes use of net-next-nuse-4.4.0 to extend support to
with the newer linux releases and thus I am now working towards bringing in
support for the latest linux kernel releases. LKL interested me because it
currently supports Linux 5.3 which is somewhat close to what I am trying to
achieve (support for latest kernels could be added with little more work).
up all the host operations and important structures like
I had initially come up with a solution to make this integration. I set
lkl_host_ops(threads,mutexes,semaphores,debug, etc.) and mapped LKL
networking syscalls to our socket calls made in DCE. I then loaded the
liblkl.so as a shared library in DCE and then called an initialization
function which maps all the DCE and shared linux library functions to
respective functions for host simulation scripts to run, also sets up the
netdevices and also calls lkl_start_kernel(...). This is an abstract
summary of what I specifically did to integrate LKL.
execute, but on blocking network operations such as accept(...) the
On testing the above, I found that things did build, compile and
applications got stuck. This was because the LKL kernel scheduler was not
scheduling the DCE threads and thus the client applications could not
execute a corresponding connect(...) call, which leads to the server thread
to be sleeping on an infinite timeout on schedule_timeout(..) and
inet_wait_for_connect(...).
kernel scheduler.
To solve the above problem, I tried to make some changes into the LKL
sleep for the given timeout , call the DCE scheduler first to execute the
I did the following things :
For every schedule_timeout, I put the current DCE calling thread to
other DCE threads sleeping in the queue, and call the LKL kernel scheduler.
In inet_wait_for_connect, after we prepare_to_wait_exclusive(...) toput the task in a TASK_INTERRUPTIBLE state, put to sleep the current
calling DCE thread and call the DCE scheduler.
Note : I did not change the schedule(...) function as some init callsin start_kernel(...) required scheduling other workqueue etc., and if we
did switch the task(before start_kernel returns), we would start another
DCE thread that would use the kernel stacks which haven't been initialized
yet.
thread, control switched to the second thread, and a socket(...) LKL
After I did the above changes, after the accept call by the first DCE
syscall was invoked, but this time the lkl_syscall(...) entered a deadlock
on getting the cpu lock on lkl_cpu_get(...)
lock at any particular time (as far as I understood the architecture, do
This was probably because only the host thread could be holding the cpu
correct me if I’m going wrong).
inconsistent and would obviously lead to failures but even if it doesn't
Even if we ran lkl_cpu_change_owner for every syscall, it would be
fail, LKL would guarantee it fails. LKL probably works on the idea that
only one host thread acquires the lock and thus when we manually make the
previous thread drop the lock using lkl_cpu_put, make the current thread as
host using set_thread_flag(TIF_HOST_THREAD) and then change the cpu owner,
the subsequent syscalls would fail as the cpu.count keeps increasing which
has an upper bound of 1.
https://github.com/direct-code-execution/ns-3-dce/blob/master/model/task-manager.cc#L414
A few important points to consider about DCE :
DCE uses Fibres (Light Weight Threads LWP)
DCE Task Scheduler can be found here :
DCE loads the linux kernel as a shared libraryin DCE and mapped through macros. For example : every socket(..) call in a
DCE makes use of libc hijacking, i.e. some libc functions are rewritten
simulation script leads to calling dce_socket(...) which further makes a
lkl_syscall(_NR_socket,..) inside the loaded LKL library.
Would add more details as required to better understand the problemstatement
possible solutions and propose ideas on how we should approach to integrate
It would be great if the LKL community could help me figure out
LKL into DCE.
Thank You,
Parth Pratim Chatterjee
