Memory fragmentation

Yes, this is possible. And it often occurs in loaded applications.

There are many solutions to this situation. For example, custom allocators. Let the application need to allocate many times the memory for small objects. The custom allocator allocates slightly larger memory (rounding to a multiple of 2 in power). The allocator allocates one large amount of memory at the start and splits it into sections for 2b8, for 2b10 (and so on). With the right approach, though, the allocator will be spend more memory, but there will be no fragmentation. The destructor does not return the memory back to the system, but simply marks it as free.

For some reason, the question aroused interest again. So I took it and tried it. It's always nice to learn something new.

Summary report:

It turned out that in ubuntu, if the soft limit is not set, then instead of the expected ENOMEM, we get SIGKILL from the kernel.

On a 64-bit virtual machine with a giga of RAM and 2.5 gigs of swap at malloc (1000), this process lasts only 1.5 minutes !!! (So let's assume that I was just joking, claiming "that they don't live that long").

After after setting the limit on virtual memory (800 megas), malloc still began to return 0, and I checked the issue of fragmentation.

Indeed, having freed 80 megas of realloc "in place" (reducing each block by 100 bytes), could not allocate 1000 bytes of malloc, and it was possible to get 50 bytes each, as it is not difficult to guess, only half of the previously freed memory.

(If the test program is interesting to someone, then write, tomorrow I will insert it in addition the answer.)

(probably better late than never -))

/* https://drive.google.com/file/d/0BzY1LBmZNGbwbUYtNS01VWVXUG8/view?usp=sharing
  show memory fragmentation

  use ulimit -a for look limits
  ulimit -S -v NNNNN for see malloc returns 0 and try realloc show
  or
  ulimit -S -v unlimited  for SIGKILL if no more memory
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include <string.h>
#include <signal.h>
#include <errno.h>
#include <setjmp.h>
#include <sys/sysinfo.h>
#include <unistd.h>
#include <sys/wait.h>

#include <time.h>


struct memblk {
  struct memblk *next;
  size_t mbsize;
  char   d[];
};

struct data {
  void *addr;
  size_t nb;
};

#define M1 (1024 * 1024)
#ifndef SWAP_BOUND
#define SWAP_BOUND 10 
/* когда мы выберем весь freeram и freeswap (величины при запуске программы) 
   кроме SWAP_BOUND доли swap (например 50 это 1/50-я), 
   мы начинаем слать данные о выделяемой памяти по пайпу для печати 
   окончательного результата 
   (поскольку тут уже в любой момент можем получить SIGKILL от ядра)
*/
#endif

sigjmp_buf jmp;
int signo = 0;

void
catch (int sig)
{
  signo = sig;
  siglongjmp(jmp, sig);
}

/*
  время в миллисекундах
 */
static long long
mtime()
{
  struct timeval t;

  gettimeofday(&t, NULL);
  long long mt = (long long)t.tv_sec * 1000 + t.tv_usec / 1000;
  return mt;
}

int 
main (int ac, char *av[])
{
  size_t mbsize = av[1] ? atoi(av[1]) : 1000,
    n1000 = 0, s1000 = 0;
  struct memblk *l1000 = 0,
    *p;
  struct sysinfo info;
  sysinfo(&info);
  printf("total(free)ram: %ld (%ld)  total(free)swap: %ld (%ld) (in %d units)\n", 
     info.totalram, info.freeram, info.totalswap, info.freeswap, 
     info.mem_unit);
  int chan[2];
  pipe(chan);
  struct data tr = {0};
  long long start = mtime();
  pid_t child;

  if (child = fork()) {
    close(chan[1]);
    int s, crit = 0;
    while (read(chan[0], &tr, sizeof(tr)) == sizeof(tr))
      crit++;
    pid_t p = wait(&s);

    if (crit)
      printf("Fin %d critical blocks\n"
         "total %ld blocks %ld bytes (%f MB) %lld msec\n",
         crit, 
         (long)tr.nb, (long)(tr.nb * mbsize), 
         ((double)(tr.nb * mbsize)) / M1, mtime() - start);
    else
      printf("no final critical data  %lld msec\n", mtime() - start);

    if (p == child)
      if (WIFEXITED(s))
    exit(WEXITSTATUS(s));
      else
    raise(WTERMSIG(s));
    return puts("unexepcted exit");
  }


  int sig;
  for (sig = 1; sig < 64; sig++)
    if (signal(sig, catch) == SIG_ERR)
      printf ("err signo %d\n", sig);
  
  if (sig = sigsetjmp(jmp, 0)) {
    printf ("catch sig %d (signo %d)\n",
        sig, signo);
    exit(0);
  }

  int done = 0;
  while (p = (typeof(p))malloc(mbsize)) {
    p->mbsize = mbsize;
    p->next = l1000;
    l1000 = p;
    n1000++;
    s1000 += mbsize;
    if (n1000 % M1 == 0)
      printf ("%ld blocks %ld bytes (%f MB) %lld msec\n",
          (long)n1000, (long)s1000, ((double)s1000) / M1, mtime() - start);
    else if (n1000 * mbsize > info.freeram * info.mem_unit + info.freeswap * info.mem_unit  - info.freeswap * info.mem_unit / SWAP_BOUND) {
      tr.nb = n1000;
      tr.addr = p;
      write(chan[1], &tr, sizeof(tr));
      if (!done)
    done = 1, printf("begin crit: %ld\n", (long)tr.nb);

    }
  }

  printf ("End %ld blocks %ld bytes (%f MB) %lld msec\n",
      (long)n1000, (long)s1000, ((double)s1000) / M1, mtime() - start);
  close(chan[0]);
  close(chan[1]);
  if (p = malloc(5))
    puts ("malloc(5) yes");
  printf ("malloc(50) %s\n", malloc(50) ? "yes" : "no");

  typeof (p) prev = 0, t;
  size_t save = 0, d = mbsize / 10;
  start = mtime();
  for (p = l1000; p; p = p->next) {
    if (t = realloc(p, p->mbsize - d)) {
      t->mbsize -= d;
      if (t != p) {
    puts ("new addr");
    if (prev)
      prev->next = t;
    else
      l1000 = t;
      }
      prev = p = t;
      save += d;
    } else {
      puts ("can't realloc");
      exit(1);
    }
  }

  printf ("realloc d: %ld sum: %ld (%lld msec)\n",
      (long)d, (long)save, mtime() - start);
  printf ("malloc(1000) again: %s\n", malloc(mbsize) ? "yes" : "no");
  save = 0;
  while (malloc(50))
    save += 50;
  printf ("malloc(50) = %ld\n", (long)save);
      
      
  return 0;
}

You can probably achieve the defragmentation you expect with chunks smaller than 4K, but programs don't live that long.

Live, live. The gigabytes of the swap are not infinite.

I wanted to reply with a comment, but I didn't have enough space.

In order to run out of virtual memory, 64-битных systems in theory require exabytes (in practice, there is support for up to peta - , but in general - tera-).

And if we take into account that the actual amount of physical memory rarely exceeds the amount of 32Гб (take for example 4 slots of 8 GB), then a simple allocation (not reservation) of memory to theoretical (and even to practical) limits (and even fragmented by some kilobytes) will take so much time on swap operations that the required uptime of any 64-bit system orders).

So what @avp, rather right -- vryatli :)

One of two things is more likely to happen:

1. The operating system degrades.
2. The disk memory allocated for the swap will end.

Comments:

And what is the difference between spreading and reserving?

I already explained it in the comments. Redundancy is the reservation of virtual pages for any application needs, but bypassing the allocation operation for this range of physical pages.

And can the swap grow to 18 Exb? Imho, the limit is a couple of GB (depends on the OS settings, of course. I have 2 GB worth.)

The swap simply will not be allowed to grow to such limits, also discussed in the comments.

P.S.: I have already run out of comments here, so if you have any questions, I will comment in the answer, please pay attention to it.

The question is very good asked, and it is eagerly read. My answer is rather not an answer, but a question in continuation of the topic for some reason already accepted question.

Is it possible to measure the degree of data fragmentation in the memory of your application? Someone else's? Maybe it is possible to build a visual memory card with its defragmentation?

I remember in the days of xp, there were a couple of programs that were engaged in quietly defragmenting the data in RAM and sending it to the swap for a long time. but, unfortunately, I can't remember the names of these two applications now.