Memory Accounting Types (RSS, VSS)

TIOJ now offers two types of memory statistics and memory limits: RSS and VSS. These are two different aspects of memory usage of a process in Linux.

Definition

VSS (Virtual Memory Size, also abbreviated VSZ) is the total size of virtual memory space that the process has allocated from the Linux operating system. To put it simply, the allocated virtual memory space is the memory addresses that the process is allowed to read, write or execute without triggering a segmentation fault. Loading the program itself, loading shared libraries and successful calls to mmap/sbrk system calls (which are usually called by malloc or new) will increase VSS.

Meanwhile, RSS (Resident Set Size) is the total physical memory used by a process. An allocated memory page will be loaded into physical memory only when it is used (in case of program data or stack) or when it is written to. RSS also do not include swapped-out memory pages, though swapping can be ignored in TIOJ because it is always disabled.

Linux deal with memory in the units of pages (4 KiB in size); thus, RSS and VSS values will always be multiples of 4 KiB.

As an example, the following program will use approximately 200 MiB of VSS and only a little RSS: 

#include <cstdlib>
#include <cstring>
#define SIZE (50*1024*1024) // 50 MiB

// the program itself, bss section (zero-initialized)
char a[SIZE];
// the program itself, data section
// this is meant to demonstrate that even the whole array is filled with data, it is not loaded initially
// char b[SIZE] = {1} will have the same effect
struct B {
  char x[SIZE];
  constexpr B() : x{} {
    // this is calculated at compile time and the data is in the program itself, thus the program will be around 50 MiB in size
    for (int i = 0; i < SIZE; i += 4096) x[i] = 1;
  }
} b;
char *c, *d, *e;
int x;

int main() {
  // uninitialized allocation
  // calloc is aware of the fact that new pages from sbrk() are zero-initialized, so it would not write into those pages
  c = new char[SIZE];
  d = (char*)calloc(SIZE, 1);
  // reading bss section won't load pages into physical memory
  // reading data section, however, will load pages into physical memory; thus if you change a[i] to b.x[i], this will add 50 MiB to RSS
  for (int i = 0; i < SIZE; i++) x += a[i];
  // memset is aware of newly-allocated pages and avoids writing into them
  // if you change d to c or just swap Line 23/24, this will add 50 MiB to RSS
  memset(d, 0, SIZE);
}

And the following program will use approximately 250 MiB of both VSS and RSS: 

#include <cstdlib>
#include <cstring>
#include <vector>
#define SIZE (50*1024*1024) // 50 MiB

char a[SIZE];
char *c, *d;

void e() { // growing stack (moving stack pointer) itself will cause the stack space being loaded into physical memory
  volatile char f[SIZE]; // use volatile to make sure compiler won't optimize this out
  f[0] = 0;
}

int main() {
  for (int i = 0; i < SIZE; i += 4096) a[i] = 0;
  std::vector<char> b(SIZE);
  c = (char*)malloc(SIZE);
  d = new char[SIZE](); // value-initialization
  memset(c, 0, SIZE); // if you swap this line with the previous line, c will NOT be accounted to RSS
  e();
}
Implementation

TIOJ limits VSS by setrlimit, and reports VSS usage using taskstats interface.
TIOJ limits RSS by the memory subgroup of cgroups, and reports RSS usage using the struct rusage returned by wait4.

If a process hits the VSS limit, the operating system will refuse to give more virtual memory space to the process. Memory allocators such as malloc and new will detect it and return NULL pointer or throw a std::bad_alloc exception. Because the error is not a fatal error, the judge cannot detect MLE caused by VSS limit violation if the VSS limit is set to the intended limit.
To partially mitigate this, TIOJ sets a slightly larger hard VSS limit than the indicated VSS limit, and checks if the final memory usage is larger than the indicated limit (before checking whether the program terminated normally).
This method, however, has its limits, and false negatives are still possible. For example, if the program tries to allocate a large block of memory at once and fails because of VSS limitation, its VSS usage can stay below the indicated limit and get around MLE detection. In normal competitive programming code where we usually don't deal with allocation errors, this will usually end up causing SIG instead, because failed memory allocation could indirectly cause SIGABRT (by an uncaught std::bad_alloc exception) or SIGSEGV (if the program dereferences the NULL pointer returned by malloc). Another possibility is that the bss and data sections alone cause the program itself to exceed the hard VSS limit, which will directly cause SIGSEGV and SIG.

On the other hand, the detection of MLE on RSS limit is reliable, because a process exceeding the RSS limit will be instantly killed by OOM killer. That is, if a program exceeds the RSS limit, it will always get an MLE. The hard RSS limit, however, are still set to be larger than the indicated limit by the output limit, since cgroups also accounts tmpfs (shmem) into a process' memory usage, and the output file is normally a file in tmpfs (unless strict mode is enabled).

Other notes
Back