Detecting and fixing Memory Issues

daan-mooij-674206-unsplash

There are two main tools I like to use for any memory related stuff in my c++ code. Following is an example code I had written as my implementation of a shared pointer. I think my code works as expected but not sure how much memory I am leaking if any.

#include <iostream>

template <typename T>
class MySharedPtr{
  public:
    MySharedPtr(T val){
      resource_ptr = new T(val);
      c_ptr = new int(1);
    };

  MySharedPtr<T>(const MySharedPtr<T> & ptr){
    std::cout << "copy constructor \n";
    resource_ptr = ptr.resource_ptr;
    (*ptr.c_ptr)++;
    this->c_ptr = ptr.c_ptr;
  }

  MySharedPtr<T>& operator=(const MySharedPtr<T> & ptr){
    std::cout << "copy assignment operator\n";
    if(this != &ptr){
      (*ptr.c_ptr)++;
      this->c_ptr = ptr.c_ptr;
      this->resource_ptr = ptr.resource_ptr;
     }
    return *this;
  }

  // delete move constructors...
  MySharedPtr(MySharedPtr && ptr) = delete;
  MySharedPtr & operator=(MySharedPtr && ptr) = delete;

  MySharedPtr & operator *(){
    return resource_ptr;
  }

  MySharedPtr* operator ->(){
    return resource_ptr;
  }

  virtual ~MySharedPtr(){
    std::cout << *c_ptr << '\n';
    if(*c_ptr > 0){
      (*c_ptr)--;
    }else{
      delete c_ptr;
      delete resource_ptr;
    }
  }

  int use_count(){
    return *c_ptr;
  }

  private:
    int * c_ptr;
  T * resource_ptr;
};

int main(){
  int x;
    MySharedPtr<decltype(x)> sp(1);
  {
    MySharedPtr<decltype(x)> sp1(2);
    sp1 = sp;
    std::cout << "use count is " << sp.use_count() << '\n';
  }
  
  sp = sp;
  std::cout << "use count is " << sp.use_count() << '\n';
  return 0;
}

Google Sanitizer

The command:

/usr/local/Cellar/gcc/8.2.0/bin/g++-8 -std=c++17 -g -o2 -fsanitize=address -fno-omit-frame-pointer shared_ptr.cpp -o shared_ptr && ASAN_OPTIONS=detect_leaks=1 ./shared_ptr

The output:

copy assignment operator
use count is 2
2
copy assignment operator
use count is 1
1

=================================================================
==25533==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 4 byte(s) in 1 object(s) allocated from:
    #0 0x526b18 in operator new(unsigned long) (/home/aarna/devel/practice/smart_ptrs+0x526b18)
    #1 0x52b50c in MySharedPtr<int>::MySharedPtr(int) /home/aarna/devel/practice/smart_ptrs.cpp:9:19
    #2 0x52b112 in main /home/aarna/devel/practice/smart_ptrs.cpp:62:28
    #3 0x7f6507f483d4 in __libc_start_main /usr/src/debug/glibc-2.17-c758a686/csu/../csu/libc-start.c:274

Direct leak of 4 byte(s) in 1 object(s) allocated from:
    #0 0x526b18 in operator new(unsigned long) (/home/aarna/devel/practice/smart_ptrs+0x526b18)
    #1 0x52b47b in MySharedPtr<int>::MySharedPtr(int) /home/aarna/devel/practice/smart_ptrs.cpp:8:26
    #2 0x52b134 in main /home/aarna/devel/practice/smart_ptrs.cpp:64:32
    #3 0x7f6507f483d4 in __libc_start_main /usr/src/debug/glibc-2.17-c758a686/csu/../csu/libc-start.c:274

Direct leak of 4 byte(s) in 1 object(s) allocated from:
    #0 0x526b18 in operator new(unsigned long) (/home/aarna/devel/practice/smart_ptrs+0x526b18)
    #1 0x52b50c in MySharedPtr<int>::MySharedPtr(int) /home/aarna/devel/practice/smart_ptrs.cpp:9:19
    #2 0x52b134 in main /home/aarna/devel/practice/smart_ptrs.cpp:64:32
    #3 0x7f6507f483d4 in __libc_start_main /usr/src/debug/glibc-2.17-c758a686/csu/../csu/libc-start.c:274

Direct leak of 4 byte(s) in 1 object(s) allocated from:
    #0 0x526b18 in operator new(unsigned long) (/home/aarna/devel/practice/smart_ptrs+0x526b18)
    #1 0x52b47b in MySharedPtr<int>::MySharedPtr(int) /home/aarna/devel/practice/smart_ptrs.cpp:8:26
    #2 0x52b112 in main /home/aarna/devel/practice/smart_ptrs.cpp:62:28
    #3 0x7f6507f483d4 in __libc_start_main /usr/src/debug/glibc-2.17-c758a686/csu/../csu/libc-start.c:274

SUMMARY: AddressSanitizer: 16 byte(s) leaked in 4 allocation(s).

The explanation: The address sanitizer has precisely pointed out the line numbers. It is very useful in coming up with a fix.

Valgrind

Command:

valgrind --tool=memcheck  --leak-check=full --show-leak-kinds=all --track-origins=yes  ./smart_ptrs

The output:

[aarna@localhost practice]$ valgrind --tool=memcheck --leak-check=full --show-leak-kinds=all --track-origins=yes ./smart_ptrs
==25564== Memcheck, a memory error detector
==25564== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==25564== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==25564== Command: ./smart_ptrs
==25564==
==25564==Shadow memory range interleaves with an existing memory mapping. ASan cannot proceed correctly. ABORTING.
==25564==ASan shadow was supposed to be located in the [0x00007fff7000-0x10007fff7fff] range.
==25564==Process memory map follows:
0x000000400000-0x00000055d000 /home/aarna/devel/practice/smart_ptrs
0x00000075c000-0x00000075d000 /home/aarna/devel/practice/smart_ptrs
0x00000075d000-0x000000760000 /home/aarna/devel/practice/smart_ptrs
0x000000760000-0x000001447000
0x000004000000-0x000004022000 /usr/lib64/ld-2.17.so
0x000004022000-0x000004036000
0x00000403f000-0x000004055000
0x000004221000-0x000004222000 /usr/lib64/ld-2.17.so
0x000004222000-0x000004223000 /usr/lib64/ld-2.17.so
0x000004223000-0x000004224000
0x000004224000-0x000004225000
0x000004a24000-0x000004a25000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/vgpreload_core-amd64-linux.so
0x000004a25000-0x000004c24000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/vgpreload_core-amd64-linux.so
0x000004c24000-0x000004c25000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/vgpreload_core-amd64-linux.so
0x000004c25000-0x000004c26000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/vgpreload_core-amd64-linux.so
0x000004c26000-0x000004c34000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so
0x000004c34000-0x000004e34000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so
0x000004e34000-0x000004e35000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so
0x000004e35000-0x000004e36000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so
0x000004e36000-0x000004f1f000 /usr/lib64/libstdc++.so.6.0.19
0x000004f1f000-0x00000511e000 /usr/lib64/libstdc++.so.6.0.19
0x00000511e000-0x000005126000 /usr/lib64/libstdc++.so.6.0.19
0x000005126000-0x000005128000 /usr/lib64/libstdc++.so.6.0.19
0x000005128000-0x00000513d000
0x00000513d000-0x00000523e000 /usr/lib64/libm-2.17.so
0x00000523e000-0x00000543d000 /usr/lib64/libm-2.17.so
0x00000543d000-0x00000543e000 /usr/lib64/libm-2.17.so
0x00000543e000-0x00000543f000 /usr/lib64/libm-2.17.so
0x00000543f000-0x000005456000 /usr/lib64/libpthread-2.17.so
0x000005456000-0x000005655000 /usr/lib64/libpthread-2.17.so
0x000005655000-0x000005656000 /usr/lib64/libpthread-2.17.so
0x000005656000-0x000005657000 /usr/lib64/libpthread-2.17.so
0x000005657000-0x00000565b000
0x00000565b000-0x000005662000 /usr/lib64/librt-2.17.so
0x000005662000-0x000005861000 /usr/lib64/librt-2.17.so
0x000005861000-0x000005862000 /usr/lib64/librt-2.17.so
0x000005862000-0x000005863000 /usr/lib64/librt-2.17.so
0x000005863000-0x000005865000 /usr/lib64/libdl-2.17.so
0x000005865000-0x000005a65000 /usr/lib64/libdl-2.17.so
0x000005a65000-0x000005a66000 /usr/lib64/libdl-2.17.so
0x000005a66000-0x000005a67000 /usr/lib64/libdl-2.17.so
0x000005a67000-0x000005a7c000 /usr/lib64/libgcc_s-4.8.5-20150702.so.1
0x000005a7c000-0x000005c7b000 /usr/lib64/libgcc_s-4.8.5-20150702.so.1
0x000005c7b000-0x000005c7c000 /usr/lib64/libgcc_s-4.8.5-20150702.so.1
0x000005c7c000-0x000005c7d000 /usr/lib64/libgcc_s-4.8.5-20150702.so.1
0x000005c7d000-0x000005e40000 /usr/lib64/libc-2.17.so
0x000005e40000-0x00000603f000 /usr/lib64/libc-2.17.so
0x00000603f000-0x000006043000 /usr/lib64/libc-2.17.so
0x000006043000-0x000006045000 /usr/lib64/libc-2.17.so
0x000006045000-0x00000639c000
0x00000639c000-0x00000679c000
0x000058000000-0x00005823b000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/memcheck-amd64-linux
0x00005843b000-0x00005843e000 /opt/rh/devtoolset-7/root/usr/lib64/valgrind/memcheck-amd64-linux
0x00005843e000-0x000059e40000
0x001002001000-0x001008b0a000
0x001008b8c000-0x001008bac000
0x001008bac000-0x001008bae000
0x001008bae000-0x001008cae000
0x001008cae000-0x001008cb0000
0x001008cb0000-0x001008cb1000 /tmp/vgdb-pipe-shared-mem-vgdb-25564-by-aarna-on-localhost.localdomain
0x001008cb1000-0x00100b0fd000
0x00100b1fd000-0x00100b3fd000
0x00100b4fd000-0x00100b5fd000
0x00100b7f2000-0x00100ba1b000
0x00100bbdb000-0x00100bcdb000
0x001ffeffd000-0x001fff001000
0x7ffd1941d000-0x7ffd1943e000 [stack]
0xffffffffff600000-0xffffffffff601000 [vsyscall]
==25564==End of process memory map.
==25564==
==25564== HEAP SUMMARY:
==25564== in use at exit: 32 bytes in 1 blocks
==25564== total heap usage: 1 allocs, 0 frees, 32 bytes allocated
==25564==
==25564== 32 bytes in 1 blocks are still reachable in loss record 1 of 1
==25564== at 0x4C2B955: calloc (vg_replace_malloc.c:711)
==25564== by 0x586454F: _dlerror_run (dlerror.c:141)
==25564== by 0x5864057: dlsym (dlsym.c:70)
==25564== by 0x50233B: __interception::GetRealFunctionAddress(char const*, unsigned long*, unsigned long, unsigned long) (in /home/aarna/devel/practice/smart_ptrs)
==25564== by 0x4DD462: __asan::InitializeAsanInterceptors() (in /home/aarna/devel/practice/smart_ptrs)
==25564== by 0x41A49F: __asan::AsanInitInternal() [clone .part.1] (in /home/aarna/devel/practice/smart_ptrs)
==25564== by 0x400FCA2: _dl_init (dl-init.c:116)
==25564== by 0x4001029: ??? (in /usr/lib64/ld-2.17.so)
==25564==
==25564== LEAK SUMMARY:
==25564== definitely lost: 0 bytes in 0 blocks
==25564== indirectly lost: 0 bytes in 0 blocks
==25564== possibly lost: 0 bytes in 0 blocks
==25564== still reachable: 32 bytes in 1 blocks
==25564== suppressed: 0 bytes in 0 blocks
==25564==
==25564== For counts of detected and suppressed errors, rerun with: -v
==25564== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

The explanation:

The output by valgrind shows entire picture of virtual memory and how source files and code is laid out in the memory. It detects the loss of 32 bytes of heap memory still in use at the exit.

The fix:

The output shown by the google address sanitizer was useful at micro-level. It precisely pointed the line number and I was able to apply my first fix to the memory leak in virtual destructor as follows:

virtual ~MySharedPtr(){
  if(*c_ptr > 0){
    (*c_ptr)--;
  }
  
  if(*c_ptr == 0){
    if(resource_ptr != nullptr){
      delete resource_ptr;
      resource_ptr = nullptr;
    }
    delete c_ptr;
    c_ptr = nullptr;
  }
}

I still have following leaks:

=================================================================
==9130==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 4 byte(s) in 1 object(s) allocated from:
#0 0x1026a53d0 in wrap__Znwm (libasan.5.dylib:x86_64+0x6e3d0)
#1 0x102324526 in MySharedPtr<int>::MySharedPtr(int) shared_ptr.cpp:9
#2 0x10232428a in main shared_ptr.cpp:68
#3 0x7fff7661b014 in start (libdyld.dylib:x86_64+0x1014)

Direct leak of 4 byte(s) in 1 object(s) allocated from:
#0 0x1026a53d0 in wrap__Znwm (libasan.5.dylib:x86_64+0x6e3d0)
#1 0x1023244a4 in MySharedPtr<int>::MySharedPtr(int) shared_ptr.cpp:8
#2 0x10232428a in main shared_ptr.cpp:68
#3 0x7fff7661b014 in start (libdyld.dylib:x86_64+0x1014)

SUMMARY: AddressSanitizer: 8 byte(s) leaked in 2 allocation(s).

Going through the code I fixed my copy assignment operator by deleting the resource pointer and the counter pointer as follows:

MySharedPtr<T>& operator=(const MySharedPtr<T> & ptr){
  std::cout << "copy assignment operator\n";
  if(this != &ptr){
    delete resource_ptr;  // deleting fix 1
    delete c_ptr;         // deleting fix 2
    (*ptr.c_ptr)++;
    this->c_ptr = ptr.c_ptr;
    this->resource_ptr = ptr.resource_ptr;
   }
   return *this;
}

And my code generated error free output:

copy assignment operator
use count is 2
copy assignment operator
use count is 1

Atomics & lock-free data structures c++

  • The modern microprocessor pipeline is 14 stages deep during which the programming instructions reordered all the times for optimization purposes.
  • Linux 2.6 supports full preemption, i.e. the thread can be suspended in between.
  • Atomic types are the locations in main memory to which the access is exclusive to a thread/process.
  • Barriers are used for ordering the accesses to the memory locations.
  • Atomic operations are provided at hardware level in order to make the operations indivisible.
  • The Implementation is highly dependent upon the hardware. x86 has strictest rules around memory ordering.
  • Atomic operations with memory fences prevents reordering of the instructions in order to make the operation indivisible.
  • Atomic operations are expensive because the OS and hardware can not do all the necessary optimizations.

<atomic> header provides various atomic types. Following is non-exhaustive list of atomic types

atomic_bool std::atomic<bool>
atomic_char std::atomic<char>
atomic_schar std::atomic<signed char>
atomic_uchar std::atomic<unsigned char>
atomic_int std::atomic<int>
atomic_uint std::atomic<unsigned>
atomic_short std::atomic<short>
atomic_ushort std::atomic<unsigned short>
atomic_long std::atomic<long>
atomic_ulong std::atomic<unsigned long>
atomic_llong std::atomic<long long>
atomic_ullong std::atomic<unsigned long long>
atomic_char16_t std::atomic<char16_t>
atomic_char32_t std::atomic<char32_t>
atomic_wchar_t std::atomic<wchar_t>

Operations on Atomic types

These operations take a argument for memory order. Which can be one of std::memory_order_relaxed, std::memory_order_acquire,  std::memory_order_release, std::memory_order_acq_rel,  std::memory_order_consume or  std::memory_order_seq_cst

  • load: this is read operation on an atomic type.
  • store: this is a write operation on an atomic type.
  • exchange: this is read-modify-write operation on an atomic type. All the compare operations are used as compare_exchange(expected, desired, <optional memory order>). On successful exchange it return true else it returns false.
    • compare_exchange
    • compare_exchange_weak: these are really for the architectures where the read-modify-write operation is not guaranteed atomic. It can generate spurious errors and it is advised to use in a loop. It has same effect as of compare_exchange_strong on x86 platform.
    • compare_exchange_strong: it is guaranteed to return false on failure and guaranteed to return true on success.
  • fetch_ versions of add, or etc
  • overriden operators like +=, -=, *=, |=

Lock Based implementation of a Multi-producer, Multi-consumer Queue.

producer-consumer

It is important to see the lock based data structures before implementing lock-free data structures.

/*
Code for Lock based queue.
std::queue is wrapped in a struct Queue. 
internal_queue variable maintains the queue.
Work to do is an instance of struct Work.
Queue has pop and push functions.
Push function takes the work instance by rvalue instance and 
pushes it onto the internal queue.
Pop function returns a shared pointer to Work. The shared pointer
 is used to avoid the ABA problem.
Pop function is a non blocking function.

If the queue is empty, the thread just yields.
A sleep is added in order to simulate slowness in the work..

Disadvantages of this kind of queue:
 * Whole Queue is locked during any operations in order to make 
sure there is synchronized access.
*/

#include <queue> // std::queue
#include <mutex> // for locking
#include <thread>
#include <memory> // smart pointers
#include <utility> 
#include <functional> // passing and storing lambda 
#include <iostream> // for std::cout
#include <chrono>

static long work_number = 0;

struct Work{
 // take lambda as a work and call lambda to process.
  Work(std::function<void(void)> lambda):f(lambda){};
  void operator()(){
    f(); 
   }
private:
  std::function<void(void)> f; 
};

struct Queue{
  Queue() = default;
  // Queue is not copyable or copy constructible.
  Queue(const Queue &) = delete;
  Queue & operator=(const Queue &) = delete;
  std::shared_ptr<Work> pop();
  void push(Work &&);
private:
  std::mutex mtx;
  std::queue<Work> internal_queue;
};

 void Queue::push(Work && work){
  std::lock_guard<std::mutex> lg(mtx);
  internal_queue.push(work);
 }

 std::shared_ptr<Work> Queue::pop(){
  Work w([](){});
  {
    std::lock_guard<std::mutex> lg(mtx);
    if(internal_queue.size() > 0){
      w = std::move(internal_queue.front());
      internal_queue.pop();
     }
    else
    {
     std::this_thread::yield(); // let the other threads work
   }
 }
 return std::make_shared<Work>(w);
}

struct Producer{
 Producer(Queue & q):q(q){};
 void produce(){
   for(;;){
     Work w([&](){std::cout << "work number : " << ++work_number << " is called.." << "\n";});
     q.push(std::move(w));
   }
 }
private:
 Queue & q;
};

struct Consumer{
  Consumer(Queue & q):q(q){};
   void consume(){
   for(;;){
     std::shared_ptr<Work> w_ptr = q.pop();
     Work * w = w_ptr.get();
     (*w)();
     std::this_thread::sleep_for(std::chrono::milliseconds(100));
   }
 }
private:
 Queue & q;
};

int main(){
 Queue q;
 std::thread producer_thread1([&q](){
   Producer p(q);
   p.produce();
 });

std::thread producer_thread2([&q](){
  Producer p(q);
  p.produce();
 });

std::thread consumer_thread1([&q](){
 Consumer c(q);
 c.consume();
 });

std::thread consumer_thread2([&q](){
 Consumer c(q);
 c.consume();
 });

std::thread consumer_thread3([&q](){
 Consumer c(q);
 c.consume();
 });

 producer_thread1.join();
 producer_thread2.join();
 consumer_thread1.join();
 consumer_thread2.join();
 consumer_thread3.join();
 return 0;
}

Lock Free Data Structures

In the above implementation, the data structure is a lock based one and hence no two threads can access is concurrently.

Understanding glibc malloc

sploitF-U-N

I always got fascinated by heap memory. Questions such as

How heap memory is obtained from kernel?
How efficiently memory is managed?
Is it managed by kernel or by library or by application itself?
Can heap memory be exploited?

were in my mind for quite some time. But only recently I got time to understand about it. So here I would like to share my fascination turned knowledge!! Out there in the wild, many memory allocators are available:

  • dlmalloc – General purpose allocator
  • ptmalloc2 – glibc
  • jemalloc – FreeBSD and Firefox
  • tcmalloc – Google
  • libumem – Solaris

Every memory allocator claims they are fast, scalable and memory efficient!! But not all allocators can be suited well for our application. Memory hungry application’s performance largely depends on memory allocator performance. In this post, I will only talk about ‘glibc malloc’ memory allocator. In future, I am hoping to cover up other memory allocators. Throughout…

View original post 3,632 more words

Linux Processes

process is a program in execution. Since linux represent everything in terms of files, currently running processes are also represented using /proc file system. The proc/<pid> contains open files (sockets), pending signals, process state, kernel data structures, threads of execution and data section.

Processes provides two types of virtualization

  • Virtual Processor
  • Virtual Memory

Processes are created on linux using fork() system call. When fork() is called, a process is created which is child of process who is called fork(). The reason it’s called as a child because it gets copy of resources (data, variables, code, pages, sockets etc) from it’s parent process.

The list of processes are stored in a doubly linked list called as task list. The process descriptor is type  struct task_struct defined in <linux/sched.h> .

Processes are identified by PID. PID is a defined by pid_t data structure which is an integer up to 32,768. Generally processes up to number 1024 is kernel processes and rest of them are user processes. When a new process is forked, the number is not sequential but its randomized in order to avoid being guesses. When number is processes reaches max limit, the number is reseted and starts from 1024. The limit of number of processes can be increased by setting value at proc/sys/kernel/pid_max.

Process creation

  • fork()
    • a process can create another process using fork() function.
    • It is implemented using clone()
    • fork(), vfork() and __clone() calls clone() which calls do_fork() which calls copy_process()
    • the process created is called as child process
    • Example of simple fork call:
      pid_t pid = fork();
    • if return value of fork() call is 0, fork is successful and control block is in child process.
       if (pid == 0)
          {
            printf("child process");
          }
    • if return value of fork() call is greater than 0, fork is successful and control block is in parent process process.
      else if (pid > 0)
          {
            printf("parent process");
          }
    • if return value of fork() is negative, the call is failed.
      else
          {
            printf("fork failed");
          }
    • fork() creates a child process that is a copy of the current task. It differs from the parent only in its PID, its PPID (parent’s PID), and certain resources and statistics (e.g. pending signals) which are not inherited
    • Besides the open files, other properties of the parent are inherited by the child:
      • Real user ID, real group ID, effective user ID, and effective group ID
      • Supplementary group IDs
      • Process group ID
      • Session ID
      • Controlling terminal
      • The set-user-ID and set-group-ID flags
      • Current working directory
      • Root directory
      • File mode creation mask
      • Signal mask and dispositions
      • The close-on-exec flag for any open file descriptors
      • Environment
      • Attached shared memory segments
      • Memory mappings
      • Resource limits
  • exec():
    • The exec() family of function calls creates a new address space and loads a new program into the newborn child immediately after a fork.
    • There are following variations of exec calls
      • int execl(const char *path, const char *arg, ...
         /* (char *) NULL */);
      • int execlp(const char *file, const char *arg, ...
         /* (char *) NULL */);
      • int execle(const char *path, const char *arg, ...
         /*, (char *) NULL, char * const envp[] */);
      • int execv(const char *path, char *const argv[]);
      • int execvp(const char *file, char *const argv[]);
      • int execvpe(const char *file, char *const argv[],
         char *const envp[]);
Function pathname filename fd Arg list argv[] environ envp[]
execl * * *
execlp * * *
execle * * *
execv * * *
execvp * * *
execve * * *
fexecve * * *
(letter in name) p f l v e

Process 0 and 1

Process 0 is ancestor of all processes which is also known as swapper process. This process is build from scratch during boot up. Process 0 initializes all the data structures needed by kernel, enables interrupts, and creates init process which is process 1.init process, invoked by the kernel at the end of the bootstrap procedure. It is responsible for bringing up the system after the kernel has been bootstrapped. init usually reads the system-dependent initialization files (/etc/rc* files or /etc/inittab and the files in /etc/init.d) and brings the system to a certain state. Process 1 never dies. It is a normal user process, not a system process within the kernel, but runs with superuser privileges.

State of a Process

Process can be any one of following states:

  • TASK_RUNNING
    • Process is being executed on CPU or waiting
  • TASK_INTERRUPTABLE
    • Process is sleeping/suspended.
  • TASK_UNINTERRUPTABLE
    • Process is in sleeping state but signal to these processes will not change state of the process.
  • TASK_STOPPED
    • Process being stopped.
  • TASK_TRACED
    • Process is being debugged
  • EXIT_DEAD
    • Child process is being removed because parent process issued wait4() or waitpid()
  • EXIT_ZOMBIE
    • Child process being terminated but parent has not issued wait() or waitpid()

Copy on Write – an optimization on fork()

All the data and resources that belong to the parent are not copied to child. This is done is steps and as needed. This is an optimization in order to delay copying data as needed. The another reason is in calls such as exec(), none of the parent data is actually needed, there should not be a need to copy any pages from parent.

Process Switch

During process switch the registers are saved in kernel memory area for process and loaded back when process resumes on CPU. This is was done using far jmp assembly instruction on x86. On linux 2.6 onwards software is used for context switching instead of hardware context switching. Software context switch is safer and faster.

Scheduling

Processes work on time slicing basis giving user the illusion that only the user has access to the CPU and the memory is unlimited. The scheduling of processes depend upon scheduling policy or algorithm. The scheduling algorithm must schedule in such a way that processes should have fast response, good throughput, limited use of resources and honor the priorities.

Linux processes are preemptive. A process with high priority than low priority runs first by interruption of low priority process is one is running. There are following classes of Linux processes:

  • SCHED_FIFO
  • SCHED_RR
  • SCHED_NORMAL

Scheduling factors for a process

  • static priority: between 100 (high priority) to 139 (low priority)
  • nice value: -20 (high priority) to 19 (low priority)
  • dynamic priority: between 100 (high priority) to 139 (low priority)
  • real-time priority: 1 (highest priority) to 99 (lowest priority)

Kernel Preemption

In non-preemptive kernels, kernel code runs until completion. That is, the scheduler cannot reschedule a task while it is in the kernel: kernel code is scheduled cooperatively, not preemptively. Kernel code runs until it finishes (returns to user-space) or explicitly blocks.

The Linux kernel (since 2.6), unlike most other Unix variants and many other operating systems, is a fully preemptive kernel. It is possible to preempt a task at any point, so long as the kernel is in a state in which it is safe to reschedule.

Threads

Linux threads are light weight processes i.e. Linux does not make any difference between threads and processes. They share resources with parent like heap space, file descriptors, sockets  but each thread gets own stack.

  • each thread contain TCB- a thread control block which contains following
    • Thread Identifier:Unique id (tid) is assigned to every new thread
    • Stack pointer: Points to thread’s stack in the process
    • Program counter: Points to the current program instruction of the thread
    • State of the thread (running, ready, waiting, start, done)
    • Thread’s register values
    • Pointer to the Process control block (PCB) of the process that the thread lives on
  • threads are also created with clone() system call like other processes except for some flags to clone like
    clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0);

Address Space of a Process

The address space of a process consist of linear addresses the process is allowed to use. The linear address spaces are different per process. The linear addresses are managed in form of Memory Regions. Following are examples of system calls to manage memory regions:

Syscall usage
brk()/sbrk() changing the heap size of process
execve Load a new program in the memory in the currently running process
_exit() exit the current process and delete the memory space occupied
fork() create a new (child) process, copying/referencing page tables from parent process
mmap(), mmap2() creates memory mapped file, enlarge the memory address space of the process.
mremap() Expand or shrink memory region
munmap() destroys previously mmaped memory area and shrinks memory space of the process
shmat() Attaches new memory region to the process
shmdt() Detaches new memory region to the process

List all processes

Since linux uses proc file system to represent processes, listing all the processes can be done using ls /proc/

Screen Shot 2018-03-04 at 11.24.18 PM

listing /proc/<PID>/

Screen Shot 2018-03-04 at 11.28.01 PM

The directories and files listed here represent resources like file descriptors /fd/ etc

Memory Descriptor

The address associated with a process is stored in memory descriptor with type mm_struct. All the descriptors are stored in a doubly linked list with type mmlist.

Heap Management

malloc(size): c stdlib method to request size of Dynamic memory. On success returns pointer to  first linear address. On failure returns non zero integer.

calloc(n, size):c stdlib method to request size of Dynamic memory. On success returns pointer to  first linear address, set the memory to 0. On failure returns non zero integer.

realloc(size):c stdlib method that changes the size of memory location of previously allocated memory region.

free(): frees the allocated memory.

brk(address): Modifies the heap directly

sbrk(incr): increases/decreases the memory region

brk() System call:

  • brk() is the only function that is a syscall. All the other functions listed above are implemented using brk() and mmap()
  • it allocated and deallocated whole pages since it acts on memory region.

System calls a.k.a syscalls:

syscalls are implemented in Kernel and can be called from a process running in user space with appropriate privileges. There are around 330 number of system calls in Linux. The Linux API is written in c.

Process Termination

Process termination can be normal (finishing intended code execution) or can be abnormal. The Abnormal execution is because of following reasons:

  • Kernel, the process itself or any other process send certain signal.
  • Sigfault: Process tries to access memory location which it does not have privilege of access.
  • Abnormal conditions is exit with non-zero code.

On process exit Kernel releases the memory and other resources held by the process like file descriptors.

When Parent process dies, the children of that process becomes orphan processes and the process init becomes parent of those processes. Sometimes parents do not wait for child processes after fork(). These child processes becomes zombi processes after termination. A process can wait (block) when its children are in the running state using wait or waitpid.

  • The wait function can block the caller until a child process terminates, whereas waitpid has an option that prevents it from blocking.
  • The waitpid function doesn’t wait for the child that terminates first; it has a number of options that control which process it waits for.

Linux Performance Optimization

3 main levels for tuning

  1. CPU/BIOS tuning:
  2. OS tuning:
  3. Network Tuning:

Configuration using tuned

  • tuned is available from RHEL7
  • Make changes in sysctl as well as /sys directory
  • there are profiles available for specific needs like network-latency, latency-performance, network-performance, throughput-performance, desktop and balanced etc

Screen Shot 2018-03-14 at 7.49.16 PM

Examples of the profiles

Screen Shot 2018-03-14 at 7.50.11 PM

Latency Performance Settings in Linux Tuned

Settings  Meaning
force_latency=1 processor state C1
governor=performance CPU is at higher performance state
energy_perf_bias= performance Higher performance state
min_perf_pct=100 comes from the P-state drivers. The interfaces provided by the cpufreq core for controlling frequency the driver provides sysfs files for controlling P state selection. These files have been added to /sys/devices/system/cpu/intel_pstate.
kernel.sched_min_granularity_ns=10000000 Minimal preemption granularity for CPU-bound tasks
vm.dirty_ratio=10 The generator of dirty data starts writeback at this percentage
vm.dirty_background_ratio=3 Start background writeback (via writeback threads) at this percentage
vm.swappiness=10 The swappiness parameter controls the tendency of the kernel to move processes out of physical memory and onto the swap disk. 0 tells the kernel to avoid swapping processes out of physical memory for as long as possible 100 tells the kernel to aggressively swap processes out of physical memory and move them to swap cache
kernel.sched_migration_cost_ns=5000000 The total time the scheduler will consider a migrated process “cache hot” and thus less likely to be re-migrated
net.core.busy_read=50 This parameter controls the number of microseconds to wait for packets on the device queue for socket reads. It also sets the default value of the SO_BUSY_POLL option.
sysctl.net.core.busy_poll=50 This parameter controls the number of microseconds to wait for packets on the device queue for socket poll and selects
kernel.numa_balancing=0 disable NUMA balancing
net.ipv4.tcp_fastopen=3 Linux supports configuring both overall client and server support via /proc/sys/net/ipv4/tcp_fastopen (net.ipv4.tcp_fastopen via sysctl). The options are a bit mask, where the first bit enables or disables client support (default on), 2nd bit sets server support (default off), 3rd bit sets whether data in SYN packet is permitted without TFO cookie option. Therefore a value of 1 TFO can only be enabled on outgoing connections (client only), value 2 allows TFO only on listening sockets (server only), and value 3 enables TFO for both client and server.

More information about Tunables:

  • Dependent on NUMA:
    • Reclaim Ratios
      • /proc/sys/vm/swappiness
      • /proc/sys/vm/min_free_kbytes
  • Independent of NUMA:
    • Reclaim Ratios
      • /proc/sys/vm/vfs_cache_pressure
      • Writeback Parameters
        • /proc/sys/vm/dirty_background_ratio
        • /proc/sys/vm/dirty_ratio
      • Readahead parameters
        • /sys/block/queue/read_ahead_kb

top utility

  • available on all the machines
  • default tool for measurement that has lot of information.

Parameters important for Optimization


Swappiness

  • Controls how aggressively the system reclaims anonymous memory versus
    page cache memory:

    • Anonymous memory – swapping and freeing
    • File pages – writing if dirty and freeing
    • System V shared memory – swapping and freeing
  • Default is 60
  • If it is decreased: more aggressive reclaiming of page cache memory
  • If it is Increased: more aggressive swapping of anonymous memory
  • Should be set to 0 as per the low latency optimization guide http://wiki.dreamrunner.org/public_html/Low_Latency_Programming/low-latency-programming.html

Memory reclaim watermarks:

Screen Shot 2018-03-14 at 10.54.08 PM

zone_reclaim_mode

  • Controls NUMA specific memory allocation policy
  • When set and node memory is exhausted:
    • Reclaim memory from local node rather than allocating
      from next node
    • Slower initial allocation, higher NUMA hit ratio
  • When clear and node memory is exhausted:
    • Allocate from all nodes before reclaiming memory
    • Faster initial allocation, higher NUMA miss ratio
  • To see current setting: cat /proc/sys/vm/zone_reclaim_mode
  • Turn ON: echo 1 > /proc/sys/vm/zone_reclaim_mode
  • Turn OFF: echo 0 > /proc/sys/vm/zone_reclaim_mode
  • It is recommended that the settings should be off for large in memory database server.

CPU Tuning

  • p-states
    • It’s an Advanced Configuration and Power Interface (ACPI) defined processor performance state.
    • P0, P1, P2..p11 etc are values for P-states. For highest performance the p-states should be set to P0
  • c-states
    • It allow the CPU package to shut down cores and parts of the CPU microarchitecture to save energy while balancing response times.

    • C0, C1, C3, C6 etc are the values for c-states. Here is the chart for more information

      Mode Name What it does CPUs
      C0 Operating State CPU fully turned on All CPUs
      C1 Halt Stops CPU main internal clocks via software; bus interface unit and APIC are kept running at full speed. 486DX4 and above
      C1E Enhanced Halt Stops CPU main internal clocks via software and reduces CPU voltage; bus interface unit and APIC are kept running at full speed. All socket LGA775 CPUs
      C1E Stops all CPU internal clocks. Turion 64, 65-nm Athlon X2 and Phenom CPUs
      C2 Stop Grant Stops CPU main internal clocks via hardware; bus interface unit and APIC are kept running at full speed. 486DX4 and above
      C2 Stop Clock Stops CPU internal and external clocks via hardware Only 486DX4, Pentium, Pentium MMX, K5, K6, K6-2, K6-III
      C2E Extended Stop Grant Stops CPU main internal clocks via hardware and reduces CPU voltage; bus interface unit and APIC are kept running at full speed. Core 2 Duo and above (Intel only)
      C3 Sleep Stops all CPU internal clocks Pentium II, Athlon and above, but not on Core 2 Duo E4000 and E6000
      C3 Deep Sleep Stops all CPU internal and external clocks Pentium II and above, but not on Core 2 Duo E4000 and E6000; Turion 64
      C3 AltVID Stops all CPU internal clocks and reduces CPU voltage AMD Turion 64
      C4 Deeper Sleep Reduces CPU voltage Pentium M and above, but not on Core 2 Duo E4000 and E6000 series; AMD Turion 64
      C4E/C5 Enhanced Deeper Sleep Reduces CPU voltage even more and turns off the memory cache Core Solo, Core Duo and 45-nm mobile Core 2 Duo only
      C6 Deep Power Down Reduces the CPU internal voltage to any value, including 0 V 45-nm mobile Core 2 Duo only
    • Latency for C states

      C-STATE

      RESIDENCY

      WAKE-UP LATENCY

      C0

      ACTIVE

      ACTIVE

      C1

      1 μs

      1 μs

      C3

      106 μs

      80 μs

      C6

      345 μs

      104 μs

How to Optimize

  1. Use real production system for measurement
  2. Note the state of system before change
  3. Apply the optimizations later going to come in the post.
  4. Compare state of system after applying the optimizations
  5. Tune until you get desired results.
  6. Document the changes.

Types of Tools needed

  • Tools that gather system information or Hardware
    • lscpu
    • uname
    • systemctl list -units -t service
  • Tools for measuring Performance
  • Tools for Microbenchmarking

Optimization include Benchmarking, Profiling and Tracing

  • Benchmarking
    • this is comparing performance with industry standard
    • Tools used for benchmarking
      • vmstat used for benchmarking virtual memory
      • iostat used for benchmarking io
      • mpstat multiple processor
  • Profiling gathering information about hot spots
  • Tracing

Based on the Benchmarking, Profiling and Tracking the system is tuned as follows;

  • using echo into /proc
    • The settings are not persistent. Stay until reboot.
    • /proc files system has pid directories for processes, configuration files and sys directory
      • /proc/sys directory has some important directories like /kernel, /net, /vm , /user etc.
      • /proc/sys/vm has settings for with virtual memory.
  • Using sysctl command
    • sysctl it’s a service
    • Persistent settings.
    • It’s started at the boot time’s
    • It reads settings from a configuration file at /etc directory
    • There are some more settings in
      • usr/lib/sysctl.d stores the default
      • /run/sysctl.d stores the runtime
    • /etc/sysctl.d stores runtime settings
  • Using loading/unloading of kernel modules and configure kernel parameters
    • Using modinfo to gather information about available parameters
    • Using modprobe for modifying parameters
    • modprobe modulename key=val
    • for persistent settings, /etc/modprobe.d modulename.conf

Linux Memory Management

Memory Address

For x86 Architecture there are 3 types of addresses:

  • Logical Address:
    • This address is address of an instruction or data in machine language
    • This address consist of a segment and an offset i.e. distance from segment start address.
  • Linear address or Virtual address:
    • This address is a binary number in virtual memory that enables a process to use a location in main memory independently of other processes and to use more space than actually exists in primary storage by temporarily relegating some contents to a hard disk or internal flash drive.
  • Physical Address:
    • Address of the memory cells in RAM of the computer.

Need for Virtual Addressing

  • The main memory (RAM) available for a computer is limited.
  • Many processes use a common code in libraries.
  • Using Virtual addressing, a CPU and Kernel gives an impression to a process that the memory is unlimited.

Address Translation

  • Since 2 out of 3 address are virtual mentioned above, there is a need for address translation from Logical to Linear and Linear to Physical address.
  • For this reason each CPU contains a hardware names as Memory Management Unit (MMU).
  • Segmentation Unit: converts the Logical address to Linear.
  • Paging Unit: converts Linear address to Physical.
  • The address translation from linear address is done using two translation tables
    • Page Directory
    • Page Table

memoryTranslation

Image Credit: https://manybutfinite.com/post/memory-translation-and-segmentation/

Address Translation in Intel x86

address_translation

Linear-Address Translation to a 4-KByte Page using IA-32e Paging

address_translation_format

Formats of CR3 and Paging-Structure Entries with PAE Paging

MMU

MMU

Image Credit: By Mdjango, Andrew S. Tanenbaum (Own work) [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons

Segmentation and Paging in Linux

  • Both segmentation and Paging is redundent and hence Linux use segmentation in limited way.
  • Segmentation can assign a different linear address space to each process
  • Paging can map the same linear address space into different physical address spaces.

Segments and their usage

  • Each segment is described by 8-byte Segment Descriptor.
  • These descriptors are defined in Global Descriptor Table (GDT) or in the Local Descriptor Table(LDT).

segments

Image credit: By John Källén (jkl at commons) (Own work) [Public domain], via Wikimedia Commons

Types of Segment Descriptors

  • Code Segment Descriptor
  • Data Segment Descriptor
  • Task State Segment Descriptor

Segmentation in Linux

linuxFlexibleAddressSpaceLayout

image credit https://manybutfinite.com/post/anatomy-of-a-program-in-memory/

Data structures for segmentation

  • GDT Global Descriptor Table
    • There is one GDT per CPU in Linux.
    • There are 18 descriptors in each GDT for various purposes as follows:
      • Descriptors for Kernel code and User code.
      • Task State Segment (TSS)
      • default Local Descriptor Table (LDT)
      • Thread-Local Storage (TLS) segments
      • Advanced Power Management (APM )
      • Plug and Play (PnP ) BIOS services
      • Special segment used for handling exceptions.

 

Image Credit: Lars H. Rohwedder (User:RokerHRO – selfmade work

Paging


  • paging unit translates linear addresses into physical ones
  • For efficiency the linear addresses are divided in fixed length intervals called as pages. These continuous linear addresses within a page are mapped into continuous physical addresses.
  • Page frames: main memory is divided into fixed lenght page frames. Each page frame contains a page. Page is just block of data in memory or disk.
  • page tables: The data structures that map linear to physical addresses.
  • Page Size: 4 KB
  • Huge Pages: 2 MB and 1 GB.
  • Page address (32 bit) = Directory (10 bits) + Page Table (10 bits) + Offset(12 bit)

Physical Address Extension (PAE)

  • In order to use more than 4 GB memory Intel started using 36 pins for address translation effectively supporting more addresses.

Caching in Hardware

  • There are atleast 3 levels of caches supported in modern microprocessor.
  • The caches work on principle of spatial locality and principle of temporal locality.
  • Cache is devided into cache line generally of 64 bytes.
  • Most of caches are N-way associative.
  • Cache unit resides between the paging unit and the main memory.
  • It includes both a hardware cache memory and a cache controller.
  • Each cache line has a tag and some flags that stores the status of cache line.
  • CPUs first look for address in cache before looking into main memory.
  • Flushing cache is done using write Back mechanism which is more efficient. Only cache entry is updated by CPU and the main memory is updated eventually.

Translation Lookaside Buffers (TLB)

  • This is kind of a cache used for storing recently converted addresses between linear to physical.
  • The Address Translation unit first looks in TLB for physical address for given linear address if not found, the hardware goes through page tables to find the page.

xeon_cach_structure

Process page tables

  • Linux stores pages using 4 levels
  • Page Global Directory
  • Page Upper Directory
  • Page Middle Directory
  • Page Table
  • Each process has its own Page Global Directory and its own set of Page Tables.
  • Linear addresses from 0x00000000 to 0xbfffffff can be addressed when the process runs in either User or Kernel Mode.
  • Linear addresses from 0xc0000000 to 0xffffffff can be addressed only when the process runs in Kernel Mode.

Non Uniform Memory Access

NUMA is a shared memory architecture used in today’s multiprocessing systems. Each CPU is assigned its local memory and can access memory from other CPUs in the system. Local memory access provides the best performance; it provides low latency and high bandwidth. Accessing memory that is owned by the other CPU has a performance penalty, higher latency, and lower bandwidth.

  • Access to local memory is fast, more latency for remote memory
  • Practically all multi-socket systems have NUMA
  • Most servers have 1 NUMA node / socket
  • Some AMD systems have 2 NUMA nodes / socket
  • Sometimes optimal performance still requires manual tuning.

Typical 4 node NUMA system.

Screen Shot 2018-03-14 at 7.51.21 PM

Image credit: https://videos.cdn.redhat.com/summit2015/presentations/15284_performance-analysis-tuning-of-red-hat-enterprise-linux.pdf

Processors and Memory layout in NUMA system

Screen Shot 2018-03-14 at 11.53.58 PM

Image credit: http://pages.rubrik.com/rs/794-OHF-673/images/vSphere_6.5_Host_Resources_Deep_Dive.pdf

QPI

Screen Shot 2018-03-14 at 11.58.39 PM

Image credit: http://pages.rubrik.com/rs/794-OHF-673/images/vSphere_6.5_Host_Resources_Deep_Dive.pdf

To see the NUMA nodes and which cpus are under numa nodes:

Screen Shot 2018-03-14 at 8.02.02 PM

To see the CPUs under NUMA

Screen Shot 2018-03-14 at 8.05.09 PM

NUMA system represented on my machine.

NUMAf

NUMA related tools

Screen Shot 2018-03-14 at 11.00.34 PM

Numa Settings

  • BalancingTurn off: echo 0 > /proc/sys/kernel/numa_balancing
  • NUMA locality (hit vs miss, local vs foreign)
    • Number of NUMA faults & page migrations
    • /proc/vmstat numa_* fields
  • Location of process memory in NUMA system
    • /proc/<pid>/numa_maps
  • Numa scans, migrations & numa faults by node
    • /proc/<pid>/sched

 

More info here