CONTIGUITAS

I want to impl the code in the paper, combined in the OS xv6, which is simple to read and modify here. The strategies like the page table is clear to achieve here.

Now, based on the impl of the xv6 System and the paper, I will give the below proposal. Recalling of the paper's topic: Contiguitas: "The Pursuit of Physical Memory Contiguity in Datacenters".

The causes of unmovable: the access to this page can not be blocked (cause the TLB shootdown need to close this page's access). So pick a page that the kernel holds a pointer to somewhere (or that a device is DMA-writing into), and suddenly you cannot quietly move it — every such pinned page is a nail in the door of contiguous allocation.

The Motivation:

1. Scattering unmovable pages physically block contiguous allocation (the core issue).
2. Movable pages can be defragmented via software migration, BUT doing it frequently creates excessive CPU overhead and application latency ("long downtime").

The design that we need to pattern from:

1. We want to separate them to prevent the unmovable pages from scattering around.
2. Next, we need a dynamic resizing tech here, just like what Contiguitas does.
3. Also, right in the unmovable, some management are needed to defragment, based on the size and life span of the objects.

The second design is ignored and not required here (from the perspective of hardware to promote the migration of pages).

Part 1: the three kinds of pages

Before building anything, I had to be honest about what "unmovable" even means in xv6. The paper divides allocations into three tiers, and getting the tiers right changes the whole design:

• Type-0 — PTE-only pages (user pages). Cheap to move: detach the PTE, copy, re-map. Nothing holds a direct pointer to the data.
• Type-1 — direct-map / pointer-captured pages. The address may be stored all over memory (a reverse-map problem), or it is reached through a simple offset into a linear map, so it can never be relocated. xv6 genuinely has these.
• Type-2 — live-device pages (hardware DMA). xv6 has essentially none of these.

Where do xv6's type-1 pages come from? Back to the code of xv6 — look at kvmmake(). It maps the kernel with an identity / direct map from the end of the kernel text all the way up to PHYSTOP:

// Make a direct-map page table for the kernel.
pagetable_t
kvmmake(void)
{
  pagetable_t kpgtbl;

  kpgtbl = (pagetable_t) kalloc();          // -> kalloc_unmov()
  kvmmap(kpgtbl, (uint64)etext, (uint64)etext,
         PHYSTOP-(uint64)etext, PTE_R|PTE_W);
}

Any kernel object sitting in that range is reached by a fixed offset, so moving it would break every pointer to it. That is the source of the first type in the paper's own words: "the kernel opts for faster translation of kernel objects through a simple offset into a linear map." Examples in xv6: each process's kstack, trapframe, usyscall region, every page-table page, the DMA descriptor rings, a pipe's pipe->buffer, the exec argv. Another question: does the xv6 have unmovable allocations? You may wonder that it dose not has hardware, but the kernel did use a direct map and this can not be migrated, also it dose have I/O mem. So not movable.

Now here is the crux — if these pages are scattered, every 2MB superpage block is poisoned by even one of them, and the block can never be handed out as a huge page. The figure for explanation:

Notice the division of labor in that figure. Confinement (①) and dynamic resizing (②) are software — an OS concern. The hardware migration of unmovable pages (③) is Contiguitas-HW, and it exists only for the live-device (type-2) pages. Type-1 pages are confined and never migrated, even on real hardware. Since xv6 has almost no type-2 pages, the hardware pillar is one we can simply drop. That is the second design being ignored — and it is the whole trick that makes this tractable in xv6.

Part 2: confinement — two free lists

Step 1. Confinement (two freelists and classification for the data). The first move is to stop scattering in the first place, rather than try to repair the damage. I may need to separate the mem pool into two parts: kmem_movable and kmem (with kmem_movable right beneath the kmem). For funcs, I need to add kalloc_unmov() / kfree_unmov():

// the same allocator, just two lists
struct {
  struct spinlock lock;
  struct run *freelist;        // normal (movable) pages
  struct run *freelist_unmov;  // confined (unmovable) pages
} kmem;

void *kalloc_unmov(void)   { /* grab from freelist_unmov */ }
void  kfree_unmov(void *pa){ /* return to freelist_unmov  */ }

While you may wonder: since they share the same free and alloc logic, why would we define such func?
That's definitely because the lists are separated from each other. (Though you could also use a single flag, the two-list form is clearer and mirrors the boundary.)

Then the call sites need to know which way to allocate. Most of them live in vm.c — the funcs where most calls takes places. A page-table page allocated inside walk(), the kernel root in kvmmake(), the level-1 table in mappages — those all produce type-1 pages and must come from the unmovable list. Some func like:

pte_t *walk(pagetable_t pagetable, uint64 va, int alloc) {
  ...
  if(!alloc || (pagetable = (pde_t*)kalloc_unmov()) == 0)  // was: kalloc()
    return 0;
  ...
}

Same story for the per-process type-1 allocations — kstack in proc.c, trapframe, usyscall — plus the DMA descriptors in virtio_disk.c. These funcs calls the kalloc, but we need to take a branch to process the case of the unmovable page's mapping. The moment every one of those takes the unmovable branch, the scattering stops: unmovable pages accumulate in a confined region, and the movable region is left clean.

Part 3: dynamic resizing (pressure-driven boundary)

Step 2. The dynamic resizing (pressure driven boundary). Confinement by itself just picks a fixed split. The paper's resizing makes the boundary move with load. Need a func like resize_unmov(). The difficulty: we do not got PSI (Process Stall Information) in xv6. That is — we need a counter to represent this. So we use a stand-in signal, a counter that says the movable region is under pressure, and then a resize_unmov() that moves the boundary:

// We need to track a high-water mark unmov_allocated_top
uint64 unmov_allocated_top;  // highest PA that currently holds an unmovable page

void resize_unmov() {
  // grow: grab pages from the movable region's free tail
  // shrink: we can only mostly shrink to where the
  //         last unmovable page survive (cause we cannot move it)
}

And here is where I had to be careful about software vs hardware. Also, we are not going to use HW extension to migrate the unmovable page. So when we shrink the boundary, we cannot move a type-1 page out — we can only shrink down to where the last unmovable page survives. The boundary is pressure-driven on the way up, but on the way down it is clamped by the high-water mark.

One trick that helps shrink further: while inserting mappings in the unmovable region, we just put the objects of longer at the lower addr, which can help to lower the boundary over time.

Part 4: the scattering metric

Step 3. The scattering matric. How do we know it is working? We need a number. We need to track which page are unmovable and scan physical mem in 2MB blocks to count poisoned ones (the one poisoned by unmovable page). Actually in the labs before, we have tracked this in the mem pool like kmem.ref[total_pages], despite that it is not a recommended method to collect the 4KB pages at that time. But now — be brave to do it! We can define an array like is_unmov_page[] and use the pages' addr, with 12 bits right shift as an index:

#define TOTAL_PAGES ((PHYSTOP - KERNBASE) / PGSIZE)  // 32768
#define PA2INDEX(pa) (((uint64)pa - KERNBASE) / PGSIZE)

char is_unmov_page[TOTAL_PAGES];   // index = PA >> 12

// after that, we can just start from the addr 0, and scan 64 blocks in the 128MB's total mem
int poisoned_2mb = 0;
for (uint64 b = 0; b < TOTAL_PAGES; b += 512) {   // 512 pages = 2MB
  for (uint64 i = b; i < b + 512; i++)
    if (is_unmov_page[i]) { poisoned_2mb++; break; }
}

A moment of honesty about this metric. This "% of 2MB blocks containing ≥1 unmovable page" is not the paper's Fig. 11 number. Fig. 11 measures the total unmovable memory fraction, which tends to just stay flat under confinement. My metric is a construction inspired by the paper's §2.5 observation — "7.6% of pages → 34% of 2MB pages unmovable" — that a few scattered unmovable pages amplify into a lot of poisoned blocks. It is the metric that should actually drop once confinement packs the unmovable pages together. So measure both, and don't confuse them.

We can get two matric:

• matric 1 — unmovable pages / total pages (the paper-style fraction, stays roughly flat).
• matric 2 — poisoned 2MB block / total 2MB blocks (the "does confinement actually help" one, should drop sharply).

That second matric is the interesting one because a handful of scattered unmovable pages ruin a huge number of blocks. Confinement packs them, and the poisoned count collapses even though the total unmovable byte count barely changed.

Part 5: the deeper — dynamic huge pages

Step 4: the deeper. This part keeps the original content from my abstract.md:

What this paper wants to do is to make the memory consistent. However, the result from Meta's research shows that almost 23% of servers do not have a contiguous 2MB block!

So, we did this separation. I do recall that the method I used to achieve the 2MB huge table is HugeTLB, a static method. Despite this method being recommended, I want to improve it with a dynamic method — THP — that is, to find the 2MB dynamically, since the movable region has many consistent areas where we can compact them and put them into the dynamic 2MB pool for huge pages.

(Do not forget that we will use the trick of the migration in the movable region to defragment, but the TLB shootdown is a big cost! This is a trade-off, expecting that the defrag can compensate for this.)

That "TLB shootdown is a big cost" is exactly what this cross-core migration timeline shows:

So the whole shape of the thing is: confinement of the pages you cannot move, dynamic resizing of that region, a scanner that proves the poisoning drops, and only then pay TLB shootdowns to carve clean 2MB chunks out of the now-contiguous movable region. It is a nice piece of engineering — and the fact that xv6 makes a real, type-1 unmovable class out of its direct map is exactly why it is a good testbed for the idea. It is the end.