title: Faster way to move memory page than mremap()?
body: <p>I've been experimenting with mremap(). I'd like to be able to move virtual memory pages around at high speeds. At least higher speeds than copying them. I have some ideas for algorithms which could make use of being able to move memory pages really fast. Problem is that the program below shows that mremap() is very slow  -- at least on my i7 laptop -- compared to actually copying the same memory pages byte by byte.</p>
  
  <p>How does the test source code work? mmap() 256 MB of RAM which is bigger than the on-CPU caches. Iterate for 200,000 times. On each iteration swap two random memory pages using a particular swap method. Run once and time using the mremap()-based page swap method. Run again and time using the byte-by-byte copy swap methed. Turns out that mremap() only manages 71,577 page swaps per second, whereas the byte-by-byte copy manages a whopping 287,879 page swaps per second. So mremap() is 4 times slower than a byte by byte copy!</p>
  
  <p>Questions:</p>
  
  <p>Why is mremap() so slow?</p>
  
  <p>Is there another user-land or kernel-land callable page mapping manipulation API which might be faster?</p>
  
  <p>Is there another user-land or kernel-land callable page mapping manipulation API allowing multiple, non-consecutive pages to be remapped in one call?</p>
  
  <p>Are there any kernel extensions that support this sort of thing?</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;string.h&gt;
  #define __USE_GNU
  #include &lt;unistd.h&gt;
  #include &lt;sys/mman.h&gt;
  #include &lt;sys/types.h&gt;
  #include &lt;sys/errno.h&gt;
  #include &lt;asm/ldt.h&gt;
  #include &lt;asm/unistd.h&gt;    
  
  // gcc mremap.c &amp;&amp; perl -MTime::HiRes -e '$t1=Time::HiRes::time;system(q[TEST_MREMAP=1 ./a.out]);$t2=Time::HiRes::time;printf qq[%u per second\n],(1/($t2-$t1))*200_000;'
  // page size = 4096
  // allocating 256 MB
  // before 0x7f8e060bd000=0
  // before 0x7f8e060be000=1
  // before 0x7f8e160bd000
  // after  0x7f8e060bd000=41
  // after  0x7f8e060be000=228
  // 71577 per second
  
  // gcc mremap.c &amp;&amp; perl -MTime::HiRes -e '$t1=Time::HiRes::time;system(q[TEST_COPY=1 ./a.out]);$t2=Time::HiRes::time;printf qq[%u per second\n],(1/($t2-$t1))*200_000;'
  // page size = 4096
  // allocating 256 MB
  // before 0x7f1a9efa5000=0
  // before 0x7f1a9efa6000=1
  // before 0x7f1aaefa5000
  // sizeof(i)=8
  // after  0x7f1a9efa5000=41
  // after  0x7f1a9efa6000=228
  // 287879 per second
  
  // gcc mremap.c &amp;&amp; perl -MTime::HiRes -e '$t1=Time::HiRes::time;system(q[TEST_MEMCPY=1 ./a.out]);$t2=Time::HiRes::time;printf qq[%u per second\n],(1/($t2-$t1))*200_000;'
  // page size = 4096
  // allocating 256 MB
  // before 0x7faf7c979000=0
  // before 0x7faf7c97a000=1
  // before 0x7faf8c979000
  // sizeof(i)=8
  // after  0x7faf7c979000=41
  // after  0x7faf7c97a000=228
  // 441911 per second
  
  /*
   * Algorithm:
   * - Allocate 256 MB of memory
   * - loop 200,000 times
   *   - swap a random 4k block for a random 4k block
   * Run the test twice; once for swapping using page table, once for swapping using CPU copying!
   */
  
  #define PAGES (1024*64)
  
  int main() {
      int PAGE_SIZE = getpagesize();
      char* m = NULL;
      unsigned char* p[PAGES];
      void* t;
  
      printf("page size = %d\n", PAGE_SIZE);
  
      printf("allocating %u MB\n", PAGE_SIZE*PAGES / 1024 / 1024);
      m = (char*)mmap(0, PAGE_SIZE*(1+PAGES), PROT_READ | PROT_WRITE, MAP_SHARED  | MAP_ANONYMOUS, -1, 0);
      t = &amp;m[PAGES*PAGE_SIZE];
      {
          unsigned long i;
          for (i=0; i&lt;PAGES; i++) {
              p[i] = &amp;m[i*PAGE_SIZE];
              memset(p[i], i &amp; 255, PAGE_SIZE);
          }
      }
  
      printf("before %p=%u\n", p[0], p[0][0]);
      printf("before %p=%u\n", p[1], p[1][0]);
      printf("before %p\n", t);
  
      if (getenv("TEST_MREMAP")) {
          unsigned i;
          for (i=0; i&lt;200001; i++) {
              unsigned p1 = random() % PAGES;
              unsigned p2 = random() % PAGES;
      //      mremap(void *old_address, size_t old_size, size_t new_size,int flags, /* void *new_address */);
              mremap(p[p2], PAGE_SIZE, PAGE_SIZE, MREMAP_FIXED | MREMAP_MAYMOVE, t    );
              mremap(p[p1], PAGE_SIZE, PAGE_SIZE, MREMAP_FIXED | MREMAP_MAYMOVE, p[p2]);
              mremap(t    , PAGE_SIZE, PAGE_SIZE, MREMAP_FIXED | MREMAP_MAYMOVE, p[p1]); // p3 no longer exists after this!
          } /* for() */
      }
      else if (getenv("TEST_MEMCPY")) {
          unsigned long * pu[PAGES];
          unsigned long   i;
          for (i=0; i&lt;PAGES; i++) {
              pu[i] = (unsigned long *)p[i];
          }
          printf("sizeof(i)=%lu\n", sizeof(i));
          for (i=0; i&lt;200001; i++) {
              unsigned p1 = random() % PAGES;
              unsigned p2 = random() % PAGES;
              unsigned long * pa = pu[p1];
              unsigned long * pb = pu[p2];
              unsigned char t[PAGE_SIZE];
              //memcpy(void *dest, const void *src, size_t n);
              memcpy(t , pb, PAGE_SIZE);
              memcpy(pb, pa, PAGE_SIZE);
              memcpy(pa, t , PAGE_SIZE);
          } /* for() */
      }
      else if (getenv("TEST_MODIFY_LDT")) {
          unsigned long * pu[PAGES];
          unsigned long   i;
          for (i=0; i&lt;PAGES; i++) {
              pu[i] = (unsigned long *)p[i];
          }
          printf("sizeof(i)=%lu\n", sizeof(i));
          // int modify_ldt(int func, void *ptr, unsigned long bytecount);
          // 
          // modify_ldt(int func, void *ptr, unsigned long bytecount);
          // modify_ldt() reads or writes the local descriptor table (ldt) for a process. The ldt is a per-process memory management table used by the i386 processor. For more information on this table, see an Intel 386 processor handbook.
          // 
          // When func is 0, modify_ldt() reads the ldt into the memory pointed to by ptr. The number of bytes read is the smaller of bytecount and the actual size of the ldt.
          // 
          // When func is 1, modify_ldt() modifies one ldt entry. ptr points to a user_desc structure and bytecount must equal the size of this structure.
          // 
          // The user_desc structure is defined in &lt;asm/ldt.h&gt; as:
          // 
          // struct user_desc {
          //     unsigned int  entry_number;
          //     unsigned long base_addr;
          //     unsigned int  limit;
          //     unsigned int  seg_32bit:1;
          //     unsigned int  contents:2;
          //     unsigned int  read_exec_only:1;
          //     unsigned int  limit_in_pages:1;
          //     unsigned int  seg_not_present:1;
          //     unsigned int  useable:1;
          // };
          //
          // On success, modify_ldt() returns either the actual number of bytes read (for reading) or 0 (for writing). On failure, modify_ldt() returns -1 and sets errno to indicate the error.
          unsigned char ptr[20000];
          int result;
          result = modify_ldt(0, &amp;ptr[0], sizeof(ptr)); printf("result=%d, errno=%u\n", result, errno);
          result = syscall(__NR_modify_ldt, 0, &amp;ptr[0], sizeof(ptr)); printf("result=%d, errno=%u\n", result, errno);
          // todo: how to get these calls returning a non-zero value?
      }
      else {
          unsigned long * pu[PAGES];
          unsigned long   i;
          for (i=0; i&lt;PAGES; i++) {
              pu[i] = (unsigned long *)p[i];
          }
          printf("sizeof(i)=%lu\n", sizeof(i));
          for (i=0; i&lt;200001; i++) {
              unsigned long j;
              unsigned p1 = random() % PAGES;
              unsigned p2 = random() % PAGES;
              unsigned long * pa = pu[p1];
              unsigned long * pb = pu[p2];
              unsigned long t;
              for (j=0; j&lt;(4096/8/8); j++) {
                  t = *pa; *pa ++ = *pb; *pb ++ = t;
                  t = *pa; *pa ++ = *pb; *pb ++ = t;
                  t = *pa; *pa ++ = *pb; *pb ++ = t;
                  t = *pa; *pa ++ = *pb; *pb ++ = t;
                  t = *pa; *pa ++ = *pb; *pb ++ = t;
                  t = *pa; *pa ++ = *pb; *pb ++ = t;
                  t = *pa; *pa ++ = *pb; *pb ++ = t;
                  t = *pa; *pa ++ = *pb; *pb ++ = t;
              }
          } /* for() */
      }
  
      printf("after  %p=%u\n", p[0], p[0][0]);
      printf("after  %p=%u\n", p[1], p[1][0]);
      return 0;
  }
  </code></pre>
  
  <p>Update: So that we don't need to question how fast 'round-trip to kernelspace' is, here's a further performance test program that shows that we can call getpid() 3 times in a row, 81,916,192 times per second on the same i7 laptop:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;sys/types.h&gt;
  #include &lt;unistd.h&gt;
  
  // gcc getpid.c &amp;&amp; perl -MTime::HiRes -e '$t1=Time::HiRes::time;system(q[TEST_COPY=1 ./a.out]);$t2=Time::HiRes::time;printf qq[%u per second\n],(1/($t2-$t1))*100_000_000;'
  // running_total=8545800085458
  // 81916192 per second
  
  /*
   * Algorithm:
   * - Call getpid() 100 million times.
   */
  
  int main() {
      unsigned i;
      unsigned long running_total = 0;
      for (i=0; i&lt;100000001; i++) {
          /*      123123123 */
          running_total += getpid();
          running_total += getpid();
          running_total += getpid();
      } /* for() */
      printf("running_total=%lu\n", running_total);
  }
  </code></pre>
  
  <p>Update 2: I added WIP code to call a function I discovered called modify_ldt(). The man page hints that page manipulation might be possible. However, no matter what I try then the function always returns zero when I'm expecting it to return the number of bytes read. 'man modify_ldt' says "On success, modify_ldt() returns either the actual number of bytes read (for reading) or 0 (for writing). On failure, modify_ldt() returns -1 and sets errno to indicate the error." Any ideas (a) whether modify_ldt() will be an alternative to mremap() ? and (b) how to get modify_ldt() working?</p>