3 years agonet: Don't pretend the proto qlock is thread safe
Barret Rhoden [Thu, 15 Dec 2016 20:34:13 +0000 (15:34 -0500)]
net: Don't pretend the proto qlock is thread safe

This one is a disaster.  AFAIK, the protocol qlock does nothing to protect
lookups from the IP hash table during input processing (either a receive
function or an advise function).

This commit merely documents this and removes the lock from protecting the
lookup (note that ipht has spinlocks internally).  I left the protocol
locks in places where it seems they might need them (TCP, around the limbo
funcs, UDP around Fsnewcall).

Here's the issue: the lifetime of conversations isn't managed properly.

Conversations are loosely refcounted, (not quite a kref), and only from
higher in the networking stack (grep closeconv).  When the last ref is
closed, then the protocol's close() happens.

At the same time, conversations are stored in per-protocol hash tables
(grep ipht).  This allows the lower half of the networking stack to find
the conversation when a packet arrives.  There is no refcount involved.
The convs are removed from the ipht during the protocol's close().

During packet recv, e.g. tcpiput, we have this:

    /* lock protocol while searching for a conversation */

    /* Look for a matching conversation */
    s = iphtlook(&tpriv->ht, source, seg.source, dest, seg.dest);

which later unlocks.


It looks like the qlock is protecting something, like the conv from
disappearing.  The "lock the conv before unlocking TCP" style implies that.
Note that in closeconv(), you have to lock the conv before decreffing too.

Here's the thing: that tcp->qlock doesn't appear to be held during any
closeconv() call - it's actually rarely held.  (limborexmit(), tcpiput(),
tcpadvise(), the latter of which does some form of conv lookup too, and
some places from devip.c).  closeconv() calls the protocol's close, which
removes the conv from the ipht.  It never locks the *proto's* qlock.

Here's a scenario:
- A conversation is set up in the ipht.  One core starts the packet
  reception, and finds the conv ('s') in the ipht.
- Meanwhile, another core calls closeconv(), then cleans up the conv,
  then calls tcpclose, and *then* removes it from the ipht.

So now we have a pointer to a conv that was closed, but not quite
freed.  Plan 9 does this nasty stuff where the convs are never freed -
just zombied until they are reused.  However, the stack actually relies
on them always being conversations.  You couldn't use a slab allocator
here properly (btw, this is partly why we have O(nr_tcp_convs)
operations at various points in the stack, and why conversations always
exist in /net/tcp/).

The way the code works now, the inbound TCP code (the one that got the
conv from the ipht) will qlock the conv, then see the state is closed,
then send a reset.

Seems ok, right?  But not if another TCP conv was created in the interim.
If the inbound code was delayed enough and a new conv was created, that new
conv would actually be the old one!  This is because convs are never really
freed and the network stack plays fast-and-loose with pointers to old

The worst case?  An inbound packet to the old conv (with its old port) gets
put in the receive queue of the new conv (with any port).  The ports don't
matter - this is after the port-to-conv lookup has happened.

The qlock(tcp->qlock) does nothing to prevent this, and as far as I can
tell, it just gives us the illusion of being thread-safe.  There may be one
'saving grace', and that is that our inbound network stack currently driven
by etherread4, and is single threaded.  Though that won't help if you
(technically) get connections on different mediums (or v6 and v4).  Also,
it's a rare race, and would require, at least for TCP, for the original
conv to be Closed, which might take time or otherwise block on etherread4()
making progress.

Solutions?  There's a lot of really nasty things involved: the weird
usage of the kref pattern, the lack of a slab allocator (which it'd be
nice to use), dealing with ipgen and the array of convs (there are
probably long-reaching assumptions about convs never going away, which
gets nasty at gen time).

A proper fix would probably involve rewriting things such that the
hashtable is a source for references, possibly with kref_get_not_zero.
That'll require all successful lookups from ipht to decref when they
are done, and a careful rewrite of closeconv() and Fsprotoclone() (which
gets a new conv).  We would *not* decref / make usable the conversation
until the protocol says it's done.  (see the nasty inuse checks in

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agonet: Remove the newconv() function pointer
Barret Rhoden [Thu, 15 Dec 2016 20:32:53 +0000 (15:32 -0500)]
net: Remove the newconv() function pointer


Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agonet: Remove unused qlock from UDP and ICMP6
Barret Rhoden [Thu, 15 Dec 2016 20:28:19 +0000 (15:28 -0500)]
net: Remove unused qlock from UDP and ICMP6

Not sure if these were left over from the Inferno port or what.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoqio: Live with Qmsg
Barret Rhoden [Wed, 21 Dec 2016 16:03:11 +0000 (11:03 -0500)]
qio: Live with Qmsg

I was worried about us losing parts of the block.  That's just the price to
pay to use Qmsg.  This is similar to recvfrom() with SOCK_DGRAM:

If a message is too long to fit in the supplied buffer, excess
bytes may be discarded depending on the type of socket the message
is received from.

The reader will need to deal with this on their own, presumably by knowing
the max amount expected (e.g. MTU) and always reading up to that amount.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agofdtap: Check for bad event queues
Barret Rhoden [Fri, 6 Jan 2017 19:38:49 +0000 (14:38 -0500)]
fdtap: Check for bad event queues

Catch them during setup, instead of when we fire the tap.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmrunkernel: correctly set up page tables for all of memory
Ronald G. Minnich [Mon, 21 Nov 2016 16:55:51 +0000 (08:55 -0800)]
vmrunkernel: correctly set up page tables for all of memory

For some reason I only set it up for memory used by
ELF segments. This makes zero sense when viewed in the
cold, hard, light of a new day.

Change-Id: I01ead9986f89b2a8697cbd5359e188a0ea66d883
Signed-off-by: Ronald G. Minnich <rminnich@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agosmbios: make sure it's at f0000
Ronald G. Minnich [Thu, 5 Jan 2017 20:44:47 +0000 (12:44 -0800)]
smbios: make sure it's at f0000

it's in the spec.

Change-Id: Icd2a4d75c267a65efd234a52faa6d83af3bbf0fe
Signed-off-by: Ronald G. Minnich <rminnich@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agommu64: for completeness sake, define PML4_REACH (XCC)
Ronald G. Minnich [Fri, 6 Jan 2017 21:03:59 +0000 (13:03 -0800)]
mmu64: for completeness sake, define PML4_REACH (XCC)

Reinstall your kernel headers

Change-Id: I7f00acb4572a2560af15e70935a556ae3778601f
Signed-off-by: Ronald G. Minnich <rminnich@gmail.com>
[xcc warning]
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmrunkernel: allow loading of an SMBIOS table
Ronald G. Minnich [Wed, 4 Jan 2017 23:00:00 +0000 (15:00 -0800)]
vmrunkernel: allow loading of an SMBIOS table

The -t option will let you name an SMBIOS (t)able.
This seems to work although we're still having other
issues with our guest kernel.

Change-Id: I26f3092421a85c578da050a986a07eb61b16bff1
Signed-off-by: Ronald G. Minnich <rminnich@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agocapdev: link capability device table
Fergus Simpson [Wed, 4 Jan 2017 18:13:54 +0000 (10:13 -0800)]
capdev: link capability device table

Link the capability device table into the device table.

Change-Id: Ia441b156b73a552941cc9b0b3e025a99e2a14fc7
Signed-off-by: Fergus Simpson <afergs@google.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmrunkernel: fix formatting
Ronald G. Minnich [Tue, 3 Jan 2017 18:37:08 +0000 (10:37 -0800)]
vmrunkernel: fix formatting

This was done with emacs indent-region.

This is prior to a real change, coming next.

Change-Id: Ie9a9a4a8301634789c77630b47e1afef771d7b8b
Signed-off-by: Ronald G. Minnich <rminnich@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoVMX: change msr emulation to pass in the vm trapframe
Gan Shun Lim [Wed, 14 Dec 2016 03:08:31 +0000 (11:08 +0800)]
VMX: change msr emulation to pass in the vm trapframe

Now that we are beginning to run multiple cores, there's a need to know
which guest core we are emulating the msr access for. Rather than pass in
the guest core, we just pass in the vm_tf instead.

Change-Id: Ibecf9e462201c9a86cbfa478e1020081ad24f545
Signed-off-by: Gan Shun Lim <ganshun@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoVMM: Don't flush the EPT unnecessarily
Barret Rhoden [Fri, 2 Dec 2016 19:52:52 +0000 (14:52 -0500)]
VMM: Don't flush the EPT unnecessarily

We don't need to flush it when we load/unload the GPC, in general.  It's
more like flushing a TLB entry.

We still flush it when unloading the VMCS, since that's when we're leaving
the core for good.  There's a bit of paranoia there: we don't want any old
mappings around that other EPTs could use.  But I don't think that's

The main thing is that lazy unload only works per-process.  When the
process leaves the core, we unload then too (__abandon_core()).  That's
when we need to flush the EPT entries: when the process leaves the core.
Otherwise, we could have an old mapping that doesn't get flushed, since
Akaros didn't send the tlb_shootdown() to the core.

Here's the scenario: (for a process 'P1')
- Lazy unload
- Abandon core, no longer belongs to P1
- Another core changes a mapping, sends TLB shootdowns to all cores of
- Allocate original core to P1
- P1 runs VM, same EPT.  Still has old mappings.

This is also a concern with cr3 and the regular KPT, which is why we
need to manage the EPT's TLB mappings similarly as the KPT.  I think the
current code is OK, but we should probably check it out.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoVMM: Lazily unload the VMCS
Barret Rhoden [Fri, 2 Dec 2016 19:22:22 +0000 (14:22 -0500)]
VMM: Lazily unload the VMCS

The idea is that when we unload a GPC, we keep the VMCS, and maybe a few
other things, loaded.  Then later when we need the VMCS loaded, if we're
on the same core, we're fine.  If we're not, then we tell the other core
to flush it and then we'll load the VMCS.

Note that we clear/unload the VMCS when the process leaves the core.
This is necessary for three reasons:
- Need to not have GPC references once the proc is freed (note the
  decref in __abandon_core()).
- We don't want to send unexpected interrupts to cores belonging to
  other processes.
- We need the EPT TLB entries to be unloaded, just like the KPT.  In
  previous commits/comments, this was referred to as aggressively
leaving the process's context.  Since the EPT == KPT, we need to treat
them similarly.

This commit is a little nasty (deadlock avoidance), but at least it's
contained in x86/VMX.

The change shaves off about 260ns from the loading/unloading overhead of a
guest pcore on my machine (from 1140ns to 880ns).

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoVMM: Set the host stacktop on every VMX entry
Barret Rhoden [Fri, 2 Dec 2016 19:18:51 +0000 (14:18 -0500)]
VMM: Set the host stacktop on every VMX entry

We had been assuming that if you returned to the VM, that the kernel was
still on the same stack.  That's not true - the kernel could have blocked
the kthread that handled the vmexit.  (Despite my warnings to not block in
vmexit_dispatch(), it might be safe).

This popped up as a problem when implementing lazy VMCS unload.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoPort ttcp to Akaros
Barret Rhoden [Wed, 7 Dec 2016 23:15:28 +0000 (15:15 -0800)]
Port ttcp to Akaros

The initial version of these changes came from Andrew Gallatin

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoClang-format ttcp.c
Barret Rhoden [Wed, 7 Dec 2016 23:00:02 +0000 (15:00 -0800)]
Clang-format ttcp.c

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoImport ttcp for Plan 9
Barret Rhoden [Wed, 7 Dec 2016 22:58:09 +0000 (14:58 -0800)]
Import ttcp for Plan 9

From http://p9.nyx.link/sources/contrib/bakul/ttcp.tar

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agonet: Allow snooping on ethermedium
Barret Rhoden [Wed, 7 Dec 2016 22:49:41 +0000 (14:49 -0800)]
net: Allow snooping on ethermedium

Normally, snoopy snoops on /net/ether0.  It does this by default.  You
can also pass it an ipifc, such as /net/ipifc/{0,1,2} and it'll tap at
the medium layer.

Previously, we only supported snooping on the loopback medium.  This
commit snoops on the ethernet medium.  If you do this, you won't see
ARP or stuff like that.  It's still nice.

We need this, since the mlx4 currently can't set promiscuous mode, and
without that, we couldn't see any outbound traffic.  Outbound traffic
with /net/ether0 only gets snooped if promiscuous is on.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoFix missing poperror() calls
Fergus Simpson [Thu, 8 Dec 2016 19:41:08 +0000 (11:41 -0800)]
Fix missing poperror() calls

The AHCI driver was ported from plan 9 which did not have poperror. As a
result of the port poperror needed to be added, but there were some
mistakes. After a waserror every path out of a function must call
poperror or nexterror. This didn't always happen previously, so this
commit adds or moves poperror calls to make sure that a function's
ERRSTACK always gets cleared before returning.

Additionally, ERRSTACK must be deep enough for the number of waserror
calls in a function not separeted by poperror or nexterror. It was deeper
than it needed to be in a number of places so that was also fixed.

Change-Id: I4bbe5fd066ff890dc817e7d0e313ca6e07fe99bb
Signed-off-by: Fergus Simpson <afergs@google.com>
[checkpatch nit]
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoDo not have SCPs ask for vcores
Barret Rhoden [Thu, 1 Dec 2016 21:38:42 +0000 (16:38 -0500)]
Do not have SCPs ask for vcores

The kernel ignores it, but it's a waste of a syscall.  This popped up in
some syscall traces with dropbear - that uses a 2LS but isn't an MCP.  We'd
probably have the same issue with VMMs in -s mode.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoReduce KFS's fake block time
Barret Rhoden [Thu, 1 Dec 2016 21:36:41 +0000 (16:36 -0500)]
Reduce KFS's fake block time

This was hurting scp's performance.  I'll leave in the slight sleep to help
catch bugs.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoProperly report readable/writable in pipestat()
Barret Rhoden [Thu, 1 Dec 2016 18:29:05 +0000 (13:29 -0500)]
Properly report readable/writable in pipestat()

This caused select() (which calls fstat()) to think that some files were
writable when they weren't.  If the pipe had a lot of bidirection space,
you won't notice.  We'd only notice the problem if one side was clogged.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoFix #pipe's FD taps
Barret Rhoden [Thu, 1 Dec 2016 18:25:25 +0000 (13:25 -0500)]
Fix #pipe's FD taps

Previously, we were just tapping one queue of the pipe for each side
(side being Qdata0 or Qdata1).  We actually need to tap both queues for
either side.  For example, Qdata0 cares about when q[0] is readable and
when q[1] is writable.

This bug was hidden by another bug that led to select() constantly
polling and possibly by missing wakeups.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoFix racy bug in sbrk() (XCC)
Barret Rhoden [Thu, 1 Dec 2016 18:22:46 +0000 (13:22 -0500)]
Fix racy bug in sbrk() (XCC)

The compiler would have caught that if we could build with Werror
without blowing up the toolchain build.  Need to track down all of those

I didn't have a bug that led to this - just happened to notice the
compiler warning due to an unrelated bug.

Rebuild glibc.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Panic if there is no x2APIC
Barret Rhoden [Mon, 14 Nov 2016 20:42:46 +0000 (15:42 -0500)]
x86: Panic if there is no x2APIC

Most newer machines (Nehalem or later) should have one of these.  If not,
we'll panic later on when we try to turn it on.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Disable legacy USB for xhci
Barret Rhoden [Thu, 10 Nov 2016 19:51:32 +0000 (14:51 -0500)]
x86: Disable legacy USB for xhci

I'm not 100% that this works.  My machine always times out.  Perhaps there
are more magic steps to take?

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoVMM: immediately swap btw guests and ctlrs
Barret Rhoden [Wed, 9 Nov 2016 18:35:08 +0000 (13:35 -0500)]
VMM: immediately swap btw guests and ctlrs

We know we want to run the buddy thread, so we can just immediately run it.
This bypasses the scheduler loop, which is OK since we weren't really using
it for anything here - the ctlr and guest_thread are accounted as one

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Use Linux's MSR_SFMASK values
Barret Rhoden [Tue, 8 Nov 2016 23:40:29 +0000 (18:40 -0500)]
x86: Use Linux's MSR_SFMASK values

Whatever bits are set in SFMASK will be clear when we enter the kernel on a
SYSENTER/SYSCALL.  We had been paranoid and cleared everything.  Linux does
not.  The benefit to us using the same value is that we are less likely to
need to write_msr() when running a Linux VM.

The ridiculous thing is that there's no reason not to mask all the bits.
Over time, Linux actually changed theirs too.  Back in 2.6, it was just TF,
DF, and IF.  Later they added more.  Why not just mask it all?  Maybe
there's a reason.  Maybe not.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoVMM: Remove MSR autoloading [2/2]
Barret Rhoden [Tue, 8 Nov 2016 23:21:06 +0000 (18:21 -0500)]
VMM: Remove MSR autoloading [2/2]

Hopefully we'll never need this again.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoVMM: Manually save/restore certain registers [1/2]
Barret Rhoden [Tue, 8 Nov 2016 22:33:28 +0000 (17:33 -0500)]
VMM: Manually save/restore certain registers [1/2]

Autoload is expensive.  We can do better by manually saving and restoring
registers.  We do it when we finalize the contexts, which will speed up any
kernel-handled VMEXIT.  In the future, if we lazily unload guest_pcores,
we'll also get this benefit.

Additionally, we can look at the MSRs values to see if we can avoid the
write_msr(), which can help a lot, and we can also use the special helper
for accessing kern_gsbase.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Use faster accessors for MSR_KERNEL_GS_BASE
Barret Rhoden [Tue, 8 Nov 2016 22:17:25 +0000 (17:17 -0500)]
x86: Use faster accessors for MSR_KERNEL_GS_BASE

Accessing kern_gsbase is usually a read_msr or write_msr.  write_msr is
especially expensive.  However, on hardware that has access to the
instructions that access FS/GS base directly, we can use swap_gs and
gs_base accessors to work with kern_gs_base.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmm: Change decode to use stderr
Gan Shun Lim [Mon, 5 Dec 2016 06:16:00 +0000 (14:16 +0800)]
vmm: Change decode to use stderr

Using printf causes the last few prints to not show up before we bail
out. For debug purposes, we probably want fprintf stderr.

Change-Id: Iba69da4db583072f15e7bb31c5cb81849d1ab561
Signed-off-by: Gan Shun Lim <ganshun@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmx: Typo fixes
Fergus Simpson [Mon, 5 Dec 2016 22:55:55 +0000 (14:55 -0800)]
vmx: Typo fixes

Fixes some typos in vmx.c.

Change-Id: I9a0a2e6661e7fb6cb3caa2f5e4ad75339d71d804
Signed-off-by: Fergus Simpson <afergs@google.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoHandle "Unix Domain Sockets" in Rock code.
Dan Cross [Fri, 2 Dec 2016 20:52:13 +0000 (15:52 -0500)]
Handle "Unix Domain Sockets" in Rock code.

We approximate Unix domain sockets using pipes.
You can't listen() or accept() on them, but you
can read() and write() on them. Accommodate this
minimal pseudo-support by handling sockets of
PF_UNIX type in the Rock support code.

We need a more robust emulation of this family.

Change-Id: Iac4d3f3a4d77589b05ac9e52e38266a2f866602e
Signed-off-by: Dan Cross <crossd@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoMake AHCI less chatty at boot.
Dan Cross [Thu, 1 Dec 2016 17:48:34 +0000 (12:48 -0500)]
Make AHCI less chatty at boot.

Change the debugging print statements to emit less output.
In particular, don't print anything when we don't find a
relevant device.

Change-Id: I3a8dfc3d9194a594c4c8c4bf580b0836c4ab944b
Signed-off-by: Dan Cross <crossd@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
Barret Rhoden [Mon, 28 Nov 2016 18:58:10 +0000 (13:58 -0500)]

The poisoning was originally put in to help catch bugs where we run on
kernel stacks that are running somewhere else.  We haven't had a bug like
that in a long time.

Over time, the poisoning was shoe-horned to occasionally detect after we
run off the end of the stack.  It was marginal at best.  Now that we have
stack guard pages, we don't need this at all.

If we ever need this for temporary debugging, people can revert this commit
on their local branches, but I'd rather not keep this cruft around in the
main tree.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Handle double faults
Barret Rhoden [Mon, 28 Nov 2016 18:56:48 +0000 (13:56 -0500)]
x86: Handle double faults

Otherwise, when the kernel stack runs into its guard page, the core will
get stuck in an infinite loop, attempting to double fault.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoUse guard pages and KMC allocator for kstacks
Barret Rhoden [Mon, 28 Nov 2016 16:29:28 +0000 (11:29 -0500)]
Use guard pages and KMC allocator for kstacks

The main benefit is the guard pages, which allows us to rule out one source
of crazy kernel bugs: running off the end of your stack.

This allocator imports from vaddr_arena, allocs memory for the stack, and
sets up the virtual mapping.  Since the slab / KMC allocator caches
objects, these allocs and mappings are maintained until the cache either
voluntarily frees the object or a reclaim function runs.

There are a few interesting tidbits with reclaim when the time comes
(kstacks will need to set up a reclaim CB on kpages, which is where the
real pressure comes from).

The runtime allocations will come from the per-cpu magazine layer, once the
magazine is filled.  Actually, this was also happening with direct kpages
allocations previously, so there's no real change here.  It's just nice to

For those who are still paranoid, you can adjust the number of guard pages
at compile time.  =)

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoFix backtrace_list()'s wild read
Barret Rhoden [Mon, 28 Nov 2016 16:26:22 +0000 (11:26 -0500)]
Fix backtrace_list()'s wild read

FP could point to the top of the stack if its value is 0.  We shouldn't
read above the stack.

Previously, this was benign, but with the upcoming guard pages for kernel
stacks, the wild read goes into another kstack's guard page.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Put the boot PMLs and stacks in BSS
Barret Rhoden [Mon, 28 Nov 2016 04:01:43 +0000 (23:01 -0500)]
x86: Put the boot PMLs and stacks in BSS

This cuts down the size of the kernel binary by about 4 MB, due mostly
to the PML2 tables (which recently grew by 2x with the addition of the

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmap: Use {map,unmap}_segment() helpers
Barret Rhoden [Mon, 28 Nov 2016 03:24:47 +0000 (22:24 -0500)]
vmap: Use {map,unmap}_segment() helpers

map_vmap_segment() is basically a wrapper with a lock around the x86
helper map_segment().  This commit exposes that helper and uses it
directly, instead of having another version of a PTE walker.  The x86
helpers are a little more capable than the one-off functions I had in

map_segment() and unmap_segment() are a little more efficient for larger
sizes, since they just walk once and then operate on every PTE in a PT
instead of doing a fresh pgdir walk for each page.  map() will try to
use jumbo pages; pgdir_walk() assumes you want a PML1.  unmap() also
frees intermediate PTs (not for kernel mappings, of course), which will
help if we ever reuse this vmap code for userspace mappings.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmap: Make kernel intermediate mappings permanent
Barret Rhoden [Mon, 28 Nov 2016 03:19:22 +0000 (22:19 -0500)]
vmap: Make kernel intermediate mappings permanent

There are two parts to this.

1) All kernel mappings, including all potential mappings (e.g. the vmap
dynamic range) have PML4 PTEs that point to allocated PML3s (which can
be all zero).

2) No kernel intermediate mapping will ever be removed.  Once a PT
exists for a kernel mapping, that PT will exist forever, even if all of
its mappings are removed.

Now we can safely copy the boot_pgdir's kernel PML4 PTEs to processes'
pgdirs and dynamically update the mappings without modifying the pgdirs
of each process.  The outer mapping is the same for all pgdirs, and it
never changes.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Fix integer overflow in pml_for_each()
Barret Rhoden [Mon, 28 Nov 2016 03:14:33 +0000 (22:14 -0500)]
x86: Fix integer overflow in pml_for_each()

If kva + pgsize wrapped around and was 0, it'd wrongly be the MIN when
compared to start + len.  We need to subtract the sub_start before
comparing with MIN() to 'undo' the temporary overflow in the size

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Add EPTs to the boot_pmls
Barret Rhoden [Sun, 27 Nov 2016 18:40:06 +0000 (13:40 -0500)]
x86: Add EPTs to the boot_pmls

Previously, the boot page tables (set up in entry64.S) were only KPTs,
but with no space for EPTs.  If we performed any pmap functions that
assumed there were EPTs, then we'd be clobbering nearby, unused memory.

This was potentially happening for map_vmap_segment(), which innocently
called pte_write(), which assumes there is an EPT table adjacent to the
KPT.  This would only have been a problem if we were working on a boot
pml table, to include the boot_pml4.

Although the kernel will never use the EPT mappings, and those mappings
are not copied from boot_pml4 to the processes' page tables, it's safer
to always have the memory for the EPT available so that we don't have to
special case that much code.

Though for a dose of paranoia, I won't fill in the intermediate EPT
entries.  It's safe to write the memory of an EPT (e.g. pte_write()),
but since the EPT PMLs aren't linked, the walks won't go anywhere.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Use global PTEs for kernel mappings
Barret Rhoden [Sun, 27 Nov 2016 17:55:44 +0000 (12:55 -0500)]
x86: Use global PTEs for kernel mappings

The KERNBASE and kernel-load-addr mappings, built in ASM, were not using
global PTEs.  That's been broken since at least the x86_64 port.  The
rest of the KERNBASE mapping, set up in vm_init(), was using the global
entries, but the lower 512 GB (i.e., most of the RAM) was ignored.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmap: Use an arena allocator for kernel vmaps
Barret Rhoden [Sun, 27 Nov 2016 15:12:36 +0000 (10:12 -0500)]
vmap: Use an arena allocator for kernel vmaps

The kernel has a region of virtual addresses that are not mapped 1:1
with physical memory (which is the KERNBASE mapping).  We currently use
these for MMIO remapping, such as when a device wants an uncached

Previously, we were using a homemade incremental allocator to manage the
virtual addresses and did not have a nice way to free the addresses.
Now, we have an arena allocator that also allows us to free the vmaps.
We use two arenas and the outer arena's free-func to free the vmaps in
batches, amortizing the overhead of the global TLB shootdown.

Note that there are a couple things to do still for safe unmappings at
runtime.  Specifically, we need to make sure that all PML4s in the
system always have the same contents as boot_pgdir for the vmap region.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmap: Add a helper for global TLB shootdowns
Barret Rhoden [Sun, 27 Nov 2016 15:09:47 +0000 (10:09 -0500)]
vmap: Add a helper for global TLB shootdowns

The global TLB flush is an x86 thing, though other architectures might
have one too.  On x86, PTE_G means that the TLB entry won't be flushed
on a normal cr3 reload.  We use these for kernel mappings.  You have to
go through a couple extra hoops to flush those entries.

For us to dynamically change kernel virtual mappings, we'll need to
occasionally flush global TLB entries.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agovmap: Handle unaligned vaddrs on vunmap_vmem()
Barret Rhoden [Sat, 26 Nov 2016 22:03:20 +0000 (17:03 -0500)]
vmap: Handle unaligned vaddrs on vunmap_vmem()

vmap_pmem() allows the user to give us an unaligned paddr and it maps
enough pages to cover the requested region.  However, for the unmap, we
incorrectly thought we were given the vaddr of the overall mapping - not
the vaddr we returned to the caller (which was vaddr + PGOFF(paddr).

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoAllocate natural alignment with get_cont_pages()
Barret Rhoden [Wed, 23 Nov 2016 17:08:41 +0000 (12:08 -0500)]
Allocate natural alignment with get_cont_pages()

Linux code, notoriously the bnx2x driver, occasionally needs naturally
aligned contiguous page allocations.  Since the only code using
get_cont_pages() is Linux code, we can just use xalloc and get the
alignment they want.  Note that xalloc() is less efficient than the regular
allocations, due mostly to bypassing the arena's qcaches.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoConvert calls of get_cont_pages() to kpages_alloc
Barret Rhoden [Wed, 23 Nov 2016 16:58:18 +0000 (11:58 -0500)]
Convert calls of get_cont_pages() to kpages_alloc

get_cont_pages() and its 'order' interface are a mess.  Just ask for how
much memory you want, and let the allocator figure it out.

Also, get_cont_pages_node() was just pretending to do something
NUMA-related.  Remove it for now, and we can 'do the right thing' when we
figure it all out.

Linux code can still use get_cont_pages().  The semantics of that will
change shortly.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Update the ctor/dtor interface
Barret Rhoden [Tue, 22 Nov 2016 21:44:17 +0000 (16:44 -0500)]
slab: Update the ctor/dtor interface

The priv (private) field is to support parameterized callbacks.  For
instance, you might have separate kmem_caches for different parts of a

The old 'size' field was useless, since the caller should know the size of
the object (if that's even useful).

ctor can fail, and it will respect the mem flags.  I have a couple ctors in
mind that could block, so they'll need to check MEM_WAIT/MEM_ATOMIC.

I moved the dtor out of free_to_slab since the ctor needs to call free
if it failed.  I also considered adding a batch dtor interface so we can
free a chunk of objects at once, which could amortize the overhead of
freeing.  For example, if there was an expensive operation that had to
be done after freeing any object (such as a TLB shootdown), then a batch
dtor would make sense.  It turns out that I don't need this for now, so
I opted to keep the vmem paper's API.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoAdd #mem, for memory diagnostics
Barret Rhoden [Tue, 22 Nov 2016 20:57:35 +0000 (15:57 -0500)]
Add #mem, for memory diagnostics

ls \#mem for details.  Most people would be interested in #mem/free and

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoRemove old memory tests
Barret Rhoden [Tue, 22 Nov 2016 20:41:09 +0000 (15:41 -0500)]
Remove old memory tests

They are unused and just print a bunch of stuff that no one looks at.
Also, I want to remove the printing functions in lieu of better debugging

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoTracks arenas and slabs on tailqs
Barret Rhoden [Wed, 9 Nov 2016 16:12:52 +0000 (11:12 -0500)]
Tracks arenas and slabs on tailqs

Both lists are protected by the arenas_and_slabs qlock.  The all_arenas
list will be useful for #mem.  The all_kmem_caches might not be useful,
since all caches always have a source arena.  It's fine for diagnostics
for now.

The important thing is that the existence and importing links are all
managed by the same lock, so things like reclaim and #mem device ops can
happen without worrying about the read-mostly structure changing.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoarena: Connecting importers with sources
Barret Rhoden [Wed, 9 Nov 2016 15:44:44 +0000 (10:44 -0500)]
arena: Connecting importers with sources

This allows us to see all arenas and slabs that import resources from
one another.  Eventually we'll have a reclaim ktask for base_arena that
can trigger the various reclaim functions.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoPut the size in the name of kmalloc caches
Barret Rhoden [Wed, 9 Nov 2016 15:38:35 +0000 (10:38 -0500)]
Put the size in the name of kmalloc caches

This will give us better debugging output.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoMove assert in sem_down()
Barret Rhoden [Wed, 9 Nov 2016 15:37:37 +0000 (10:37 -0500)]
Move assert in sem_down()

This allows us to use qlocks before kthreads have been set up.  If we
actually will block on the qlock, then we'll still panic.  This won't
happen.  Overall, we can now use uncontested qlocks, which makes
bootstrapping a little easier.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Add the magazine and depot layers
Barret Rhoden [Mon, 7 Nov 2016 13:25:41 +0000 (08:25 -0500)]
slab: Add the magazine and depot layers

This is the per-cpu caching layer, which should increase scalability at
the cost of RAM.  The per-core 2x magazines aren't free, and the objects
in those magazines are harder to reclaim.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoAdd spin_trylock_irqsave()
Barret Rhoden [Wed, 9 Nov 2016 02:02:21 +0000 (21:02 -0500)]
Add spin_trylock_irqsave()

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Pretend to be core 0 in smp_main()
Barret Rhoden [Mon, 7 Nov 2016 12:48:55 +0000 (07:48 -0500)]
x86: Pretend to be core 0 in smp_main()

This is the function that all non-core 0 cores call during boot.  They
need to get a kernel stack, among other things, that requires the memory
allocator.  The allocator, in general, will need to know a core id, but
core_id() isn't ready yet for other cores.  Since the entire machine is
single threaded at this point, we can pretend to be core 0.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Remove obj_size from struct kmem_slab
Barret Rhoden [Mon, 7 Nov 2016 00:38:05 +0000 (19:38 -0500)]
slab: Remove obj_size from struct kmem_slab

We actually can just look at the cache itself, which tracks the object
size already.  That object size technically was the unaligned object
size, but that is mostly useless.  If we want the requested, but not
actual, object size for diagnostics, we can add tracking for it.

Note that the size is passed to the ctor/dtor.  That'll go away soon
too; I don't recall if it was something we added, or if it was in the
original slab paper, but it's mostly useless.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Stop appending a uintptr_t to small objects
Barret Rhoden [Mon, 7 Nov 2016 00:20:13 +0000 (19:20 -0500)]
slab: Stop appending a uintptr_t to small objects

Previously, when objects were in the slab layer (i.e., on a list in the
slab), they were constructed.  Because of that, we needed to append a
uinptr_t to small objects to form a linked list so as to not use the
constructed object.

Now that constructing happens above the slab layer, we can use the
memory of the object itself for the linked list.  Other than being
simpler, this saves some space and avoids fragmentation.  (consider a
256 byte item - we were adding 8 bytes, which would make it not pack
neatly into a page).

Note that small objects are all 'pro-touch', so we're allowed to use the
memory of the resource we're allocating.  This has always been true.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Move ctors/dtors to the slab layer
Barret Rhoden [Sun, 6 Nov 2016 16:45:49 +0000 (11:45 -0500)]
slab: Move ctors/dtors to the slab layer

In the upcoming magazine code, objects in the slabs are unconstructed.
Right now, they'll be constructed on demand, but shortly they will be
sitting in the depot and in magazines.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoRemove kmalloc caches above PGSIZE
Barret Rhoden [Thu, 3 Nov 2016 14:59:46 +0000 (10:59 -0400)]
Remove kmalloc caches above PGSIZE

Now that kpages_arena has qcaches, there's no need to have kmalloc
support caches of the same size.  We'll just call the memory allocator
directly.  Kmalloc still has its slab caches for sizes from [64, 2048].

Note that these sizes include the kmalloc_tag, which means that if you
ask for a power-of-two from kmalloc, internally it will ask for the next
higher power-of-two.  It has always been this way.  Eventually, I'd like
to get rid of the refcnt, so we can just use an arena directly and
ignore the alignment issues.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoarena: Use qcaches (slabs) in the arena
Barret Rhoden [Thu, 3 Nov 2016 14:46:18 +0000 (10:46 -0400)]
arena: Use qcaches (slabs) in the arena

Until we get reclaim working, once memory gets added to an arena's
qcache, it'll never be returned to the arena.  I'm not overly worried
about fragmentation, since we know the size of memory in the qcache is a
regularly-desired size.  (e.g. PGSIZE).

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Bootstrap before setting up kpages_arena
Barret Rhoden [Wed, 2 Nov 2016 22:05:23 +0000 (18:05 -0400)]
slab: Bootstrap before setting up kpages_arena

Kpages will use kmem_cache, so we should at least run the init function
first.  While we're at it, we can statically initialize the lock and list.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Move the name into the kmem_cache
Barret Rhoden [Wed, 2 Nov 2016 20:44:26 +0000 (16:44 -0400)]
slab: Move the name into the kmem_cache

Instead of pointing at an arbitrary const string.  The arena qcaches will
want dynamic strings, and they can't kmalloc them.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Import resources from a source arena
Barret Rhoden [Wed, 2 Nov 2016 19:29:49 +0000 (15:29 -0400)]
slab: Import resources from a source arena

Previously, the implication was that all slabs pull from the general memory
allocator.  Now, they will pull from their source arenas.

Careful - for small object, pro-touch caches, the slab layer assumes that
the arena is a page-aligned, memory allocator.  I considered outlawing
small objects for caches with explicit sources, but we might have explicit
memory arenas in the future (e.g. one per NUMA domains).

Most slab caches will just use NULL for their source, which means a kpages
arena for generic kernel memory.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Support 'no-touch' caches
Barret Rhoden [Wed, 2 Nov 2016 16:54:44 +0000 (12:54 -0400)]
slab: Support 'no-touch' caches

Slab allocators that are 'no-touch' will not use their source arenas for
bookkeeping.  This means that we always use a bufctl to point to objects,
instead of appending a pointer to an object and making a small linked list.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Add an arena pointer to the interface
Barret Rhoden [Tue, 1 Nov 2016 21:13:19 +0000 (17:13 -0400)]
slab: Add an arena pointer to the interface

The pointer doesn't do anything yet; that'll come later.

The transformation outside slab files was done with:

expression A;
expression B;
expression C;
expression D;
expression E;
expression F;
-kmem_cache_create(A, B, C, D, E, F)
+kmem_cache_create(A, B, C, D, NULL, E, F)

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Use a hashtable when looking up bufctls
Barret Rhoden [Sun, 30 Oct 2016 23:59:53 +0000 (19:59 -0400)]
slab: Use a hashtable when looking up bufctls

It only took 7 years or so to take care of that TODO.  Note that this is
probably slower than the old approach, which was instant.  Similar to
the arena, we use hash_helper and roll our own hash table, especially
due to allocation issues when we grow the table.

Aside from being necessary for NO_TOUCH slabs, this will save a lot of
memory when it comes to fragmentation when we use slabs for arenas.
Consider kpages_arena, which will have qcaches of pages.  That will be
pulling from slabs of 1 - 8 pages.  The one-page slab allocator will
need to have obj_size = PGSIZE and align = PGSIZE.  If we don't use the
hash and instead have the uintptr_t blob per object, we'd need two pages
per one-page-object, essentially wasting half of our memory.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Bootstrap more kmem_caches
Barret Rhoden [Sun, 30 Oct 2016 22:23:00 +0000 (18:23 -0400)]
slab: Bootstrap more kmem_caches

This statically allocates all of the boot-strapping caches.  This is not
strictly necessary, but it could be if the hash table default size was
enough to make a kmem_cache a large slab object.  At that point, we'd need
all three bootstrap caches to allocate one.  This way, we have less
bootstrapping to worry about.  We'll have more to worry about when we start
using magazines.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoslab: Use BSD_LISTs for the bufctls
Barret Rhoden [Sun, 30 Oct 2016 22:23:00 +0000 (18:23 -0400)]
slab: Use BSD_LISTs for the bufctls

The slab allocator has a long-standing TODO: BUF.  Instead of using a
hash table to lookup a large object, we just used storage in the object
itself.  This was okay, other than possible fragmentation effects, but
it meant that the slab allocator touched every object it tracked.  We'll
eventually need an option to have "NO_TOUCH" slab allocators, where they
do not touch the objects they are tracking.  To do that, we'll need a
hash table.

This commit switches the bufctl struct from a TAILQ to a BSD_LIST, which
will make the hash table entries smaller.  This also fixes a FOREACH
freeing bug. (use FOREACH_SAFE).

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoSet num_cores early in boot
Barret Rhoden [Sun, 6 Nov 2016 16:21:02 +0000 (11:21 -0500)]
Set num_cores early in boot

The memory allocator will need to know the number of cores in the
system when it is initialized.  In the future, it may also need to know
the number of NUMA domains.  Determining the number of cores is somewhat
arch-specific.  We can do it with ACPI on x86, and on any other platform
that supports it.

Our ACPI code relies on the memory allocator and does a lot more than
determine the number of cores, so we have a simple helper that just
looks at the ACPI tables, finds the XSDT, then finds the MADT, then
counts the local apics.  We'll use this as num_cores (possibly an
overestimate).  The topology code will make sure we didn't
underestimate later in boot.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoCheck booting during trace_printk()
Barret Rhoden [Sun, 6 Nov 2016 16:18:52 +0000 (11:18 -0500)]
Check booting during trace_printk()

Instead of num_cores.  This is safer, in case we set num_cores before
various per-cpu structures are set up.

The reason for this is that the memory allocator will need to know about
num_cores, and that will happen very early in the booting process.

trace_printk() will be fine if it just uses the boot object instead of
per-cpu objects during boot.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoMoving 'booting' to a header
Barret Rhoden [Sun, 6 Nov 2016 16:17:56 +0000 (11:17 -0500)]
Moving 'booting' to a header

Instead of externing it in random places.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoReplace the old page allocator with the base arena
Barret Rhoden [Fri, 28 Oct 2016 20:53:46 +0000 (16:53 -0400)]
Replace the old page allocator with the base arena

The old allocator couldn't handle higher order allocations efficiently.
As memory was used, it'd take longer and longer to find contiguous

We bootstrap the base arena and add free segments to it based on the
free memory regions of multiboot.  The kpages_arena is used for the
main pages allocator.  Right now, it's just a pass-through arena that
imports from base.  In the future, it'll have its own qcaches built in,
which will make common allocations even faster.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoAdd the arena allocator
Barret Rhoden [Fri, 28 Oct 2016 20:22:26 +0000 (16:22 -0400)]
Add the arena allocator

The arena allocator is based off of the Vmem allocator:


This will be the basis for all memory allocation.  Right now, it does
not have integrated qcaches (slabs).  That will require some work with
the slab allocator.  You can build a jumbo page allocator, using a
helper that xallocs with an alignment, which is pretty cool.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoAdd hash_helper.h for custom dynamic hash tables
Barret Rhoden [Tue, 1 Nov 2016 00:25:21 +0000 (20:25 -0400)]
Add hash_helper.h for custom dynamic hash tables

The full-fledged dynamic hashtable.c doesn't work for a lot of code that
needs more control over its hash table.  For instance, the arena
allocator needs fine-grained control over allocations and a node's list

This header is a few building-block helpers that allow you to build your
own dynamically resized hash table.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoPort hash.h
Barret Rhoden [Mon, 31 Oct 2016 23:30:31 +0000 (19:30 -0400)]
Port hash.h

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoImport hash.h from Linux
Barret Rhoden [Mon, 31 Oct 2016 23:25:09 +0000 (19:25 -0400)]
Import hash.h from Linux

Version 4.6, which was before all the arch-specific additions.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoAdd a #define for all MEM_FLAGS
Barret Rhoden [Fri, 28 Oct 2016 20:21:42 +0000 (16:21 -0400)]
Add a #define for all MEM_FLAGS

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoRemove mon_gfp()
Barret Rhoden [Thu, 27 Oct 2016 00:24:47 +0000 (20:24 -0400)]
Remove mon_gfp()

Unused, and it was a hack into the old allocator.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agomlx4: Remove page_is_free() safety check
Barret Rhoden [Thu, 27 Oct 2016 00:11:28 +0000 (20:11 -0400)]
mlx4: Remove page_is_free() safety check

With the arena allocator, it won't be easy to query the state of a given
page.  We actually could do that, if we wanted, with an arena helper
that looks up the btag for a given address, but it's a pain, it won't be
fast, and it will probably not work well with NUMA.

Considering this style of page pinning needs to change anyways, we might
as well remove it.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: Stop freeing the trampoline page
Barret Rhoden [Thu, 27 Oct 2016 00:07:42 +0000 (20:07 -0400)]
x86: Stop freeing the trampoline page

The arena allocator won't let us free something it never allocated.  The
pages[] based allocator didn't care, since we massaged the refcnts the
right way during page_alloc_init().

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoJump to a real kstack ASAP during boot
Barret Rhoden [Wed, 26 Oct 2016 23:40:50 +0000 (19:40 -0400)]
Jump to a real kstack ASAP during boot

We actually were using the bootstack, which was never actually given out
by a memory allocator, for a long time.  Eventually, we'd give it back,
when the kthread code thought it was a spare it needed to free.  This
would confuse the arena allocator, which never gave out the memory in
the first place.

Now, we'll switch to using a kernel stack that was given to us by
get_kstack() right away.  This helps both with the allocator as well as
with whatever safety checks we'll use for the kernel stacks (e.g. guard
pages).  It'd be brutal if we had one unlucky kernel stack that didn't
have the protections we thought all stacks had (or will have, in this

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agox86: set pcpui->{ts,gdt} early
Barret Rhoden [Wed, 26 Oct 2016 22:17:32 +0000 (18:17 -0400)]
x86: set pcpui->{ts,gdt} early

This allows us to set/get the stacktop with the usual, arch-independent
helper early.  I'll need this during init, before smp_boot.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoUse a helper for resetting kernel stacks
Barret Rhoden [Wed, 26 Oct 2016 20:40:37 +0000 (16:40 -0400)]
Use a helper for resetting kernel stacks

It's another arch-specific helper, but I have another case in an
upcoming commit that will need to pass the function pointer.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoIntegrate rbtrees into Akaros
Barret Rhoden [Thu, 13 Oct 2016 15:24:29 +0000 (11:24 -0400)]
Integrate rbtrees into Akaros

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoImport rbtrees from Linux
Barret Rhoden [Thu, 13 Oct 2016 14:57:04 +0000 (10:57 -0400)]
Import rbtrees from Linux

From Linux commit 9a2172a8d52c ("MAINTAINERS: Switch to kernel.org email
address for Javi Merino")

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoMove __always_inline to compiler.h
Barret Rhoden [Thu, 13 Oct 2016 15:15:26 +0000 (11:15 -0400)]
Move __always_inline to compiler.h

So other code can use it.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoRemove get_cont_phys_pages_at()
Barret Rhoden [Thu, 18 Aug 2016 17:42:20 +0000 (13:42 -0400)]
Remove get_cont_phys_pages_at()

I think this was for some weird debugging code, or maybe the old NIX mode.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoRemove page coloring
Barret Rhoden [Thu, 18 Aug 2016 16:02:22 +0000 (12:02 -0400)]
Remove page coloring

Page coloring doesn't work with contiguous memory allocators, and it
partitions all levels of the cache hierarchy, which doesn't work well with
spatial partitioning.  For instance, if we partition the L3 into 8 colors
(the number is based on the cache properties), we might be partitioning the
L1 and L2 into two colors (again, based on cache properties).  Although we
now have cache isolation in the shared LLC, we also partition a cache that
is already per-core.

The better approach is to use some sort of hardware support, such as
Intel's Cache Allocation Technology.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoRemove page refcnts
Barret Rhoden [Wed, 17 Aug 2016 21:22:10 +0000 (17:22 -0400)]
Remove page refcnts

page_decref() is just page_free(), now.  I'll do a rename in a later
commit.  We still needed to track if it was free or not for the currently
lousy memory allocator.

There might be issues with this, but if you aren't willing to potentially
break compatibility with Linux, then you'll never get anywhere.

There are a few reasons to do reference counts.  Only one we still have is
for devices that want to pin user memory for operations.  Specifically, the
mlx4 OS-bypass stuff does this.  The problem is that the user allocs memory
and gives arbitrary addresses to the device.  Instead, we should have the
device own the memory and let the user mmap the memory.  That gets rid of
any issues with locking the page, since the memory is always 'safe.'

That model doesn't work with traditional scatter-gather.  Worst case, we
can come up with something where we lock the VMR, instead of the page.
Though I'd rather come up with more explicit block data transfer

Note that the mlx4 OS-bypass is extremely dangerous now.  I think it was
always leaking memory before, btw.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoProvide a shim layer for reference counted pages
Barret Rhoden [Tue, 23 Aug 2016 20:54:38 +0000 (16:54 -0400)]
Provide a shim layer for reference counted pages

Right now, all pages are reference counted.  I'd like to try to stop doing
that to make contig allocations and maybe jumbo pages easier.  Longer term,
I'd like to get away from having a page struct too, though we'll see.

Some code, specifically mlx4, wants page allocations and to do reference
counting per page.  For that code, we provide this shim.

It actually looks like there are some bugs in mlx4's allocation/freeing
code, and how they account for fragments and references for higher-order
allocations.  Linux 4.7 seems to have the same structure, though perhaps
their are different semantics there.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoRefactor map_page_at_addr
Barret Rhoden [Tue, 16 Aug 2016 19:52:04 +0000 (15:52 -0400)]
Refactor map_page_at_addr

The pte_is_mapped() case was a little sketchy.  The page_is_pagemap() check
was a little hard to follow; it's easier if the caller tells us what to do,
instead of us inferring what to do.

This also fixes a memory leak in __hpf, where if we failed to map a
non-page-map page, we neglected to free it.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoFix bounds checks and misc errors in mm.c
Barret Rhoden [Tue, 16 Aug 2016 20:23:41 +0000 (16:23 -0400)]
Fix bounds checks and misc errors in mm.c

Some of the UMAPTOP checks could be overflowed.  There are probably more
throughout the kernel (though not for UMAPTOP).  Using the umem helper
simplifies the logic a bit.

For those curious, mprotect()s ENOMEM errno is what the man page says to
do, even though the others do EINVAL.

The printk change for create_vmr's failure is in the hopes of catching a
bug.  I occasionally see this:

cs has not created #srv/cs yet, spinning until it does....

kernel warning at kern/src/mm.c:103, from core 0: Not making a VMR,
        wanted 0x0000400000000000, + 0x00003b5100001000 = 0x00007b5100001000

[kernel] do_mmap() aborted for 0x0000400000000000 + 4096!

The do_mmap()'s printk would have truncated the top part of len (0x3b51),
if it was passed.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoRemove SYS_cache_buster (XCC)
Barret Rhoden [Tue, 16 Aug 2016 17:59:56 +0000 (13:59 -0400)]
Remove SYS_cache_buster (XCC)

"You're killing me, Buster."

Reinstall your kernel headers.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
3 years agoFix extra decref of shared_page
Barret Rhoden [Tue, 16 Aug 2016 17:55:35 +0000 (13:55 -0400)]
Fix extra decref of shared_page

We should never be freeing shared_page once it is allocated.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>