Lab lock: Parallelism/locking

In this lab you will try to avoid lock contention for certain workloads that stress the memory allocator.

Before writing code, you should make sure you have read §4: Locking from the xv6 book and studied the corresponding code.

To start the lab, update your repository and create a new branch for your solution:

$ git fetch origin
$ git checkout -b lock origin/xv6-19au

The program user/kalloctest stresses xv6’s memory allocator: three processes grow and shrink their address spaces, resulting in many calls to kalloc and kfree. kalloc and kfree obtain kmem.lock. kalloctest prints the number of test-and-sets that did not succeed in acquiring the kmem lock (and some other locks), which is a rough measure of contention:

$ kalloctest
start test0
test0 results:
=== lock kmem stats
lock: kmem: #test-and-set 222930 #acquire() 433008
=== top 5 contended locks:
lock: kmem: #test-and-set 222930 #acquire() 433008
lock: proc: #test-and-set 610 #acquire() 670
lock: proc: #test-and-set 340 #acquire() 671
lock: proc: #test-and-set 324 #acquire() 603
lock: proc: #test-and-set 294 #acquire() 625
test0 FAIL
$

acquire maintains, for each lock, the count of calls to acquire for that lock, and the count of test-and-sets that didn’t manage to acquire the lock. kalloctest calls a system call that causes the kernel to print those counts for the kmem and bcache locks (which are the focus of this lab) and for the 5 most contended locks. If there is lock contention the number of test-and-sets will be high because it takes many loop iterations before acquire obtains the lock. The system call returns the sum of the #test-and-sets for the kmem and bcache locks.

For this lab, you must use a dedicated unloaded machine with multiple cores. If you use a machine that is doing other things, the test-and-set counts that kalloctest prints will be nonsense. You can use a dedicated machine, or your own laptop, but don’t use a shared Attu machine.

The root cause of lock contention in kalloctest is that kalloc() has a single free list, protected by a single lock. To remove lock contention, you will have to redesign the memory allocator to avoid a single lock and list. The basic idea is to maintain a free list per CPU, each list with its own lock. Allocations and frees on different CPUs can run in parallel, because each CPU will operate on a different list. The main challenge will be to deal with the case in which one CPU’s free list is empty, but another CPU’s list has free memory; in that case, the one CPU must “steal” part of the other CPU’s free list. Stealing may introduce lock contention, but that will hopefully be infrequent.

Your job is to implement per-CPU free lists and stealing when one CPU’s list is empty. Run kalloctest to see if your implementation has removed lock contention and can still allocate all of free memory. Your output will look similar to below, although the specific numbers will differ. Make sure usertests still passes.

$ kalloctest
start test0
test0 results:
=== lock kmem stats
lock: kmem: #test-and-set 0 #acquire() 235284
lock: kmem: #test-and-set 0 #acquire() 105246
lock: kmem: #test-and-set 0 #acquire() 92495
lock: kmem: #test-and-set 0 #acquire() 12
lock: kmem: #test-and-set 0 #acquire() 12
lock: kmem: #test-and-set 0 #acquire() 12
lock: kmem: #test-and-set 0 #acquire() 12
lock: kmem: #test-and-set 0 #acquire() 12
=== top 5 contended locks:
lock: proc: #test-and-set 1654 #acquire() 712
lock: proc: #test-and-set 317 #acquire() 708
lock: proc: #test-and-set 285 #acquire() 638
lock: proc: #test-and-set 209 #acquire() 638
lock: proc: #test-and-set 193 #acquire() 638
test0 OK
$ usertests
...
ALL TESTS PASSED
$

Please give all of your locks initlock names that start with “kmem”.

Some hints: