Is it time to replace mmap()
Davis, Brooks
Is it time to replace mmap()? A history of userspace virtual address management interfaces and a case for a new interface.
 Okay, it's 1.30, so I'm going to go ahead and get started. I'm here to, well, my title is, is it time to replace Mmap? But it's really, my talk is really a history of virtual memory management, virtual address based management. And I give a proposal for the future that solves some of the problems we have today and some of the problems that the project I'm working on is creating. So let's see if that's any better. There, okay, there's some pickup. Yeah. Okay, is that picking up? No, does not seem to be. Audio level. Okay. Okay, is that picking up at all? It's on. It's on, yeah. Okay. I think, well, I can. Okay, let's try that then. Okay, is that more useful? Okay, so we're talking about what, I'm going to talk today about what we usually talk, call memory, but in fact what I'm talking about is virtual address space management. And that's a process of both allocating virtual address space and putting something behind it so that it doesn't give you a page fault because there's nothing there when you do it. But first we're going to, so we're going to start with some history. Here we see a timeline of a little bit of the future and the entirety of computing history. You know, you could, you could quibble a bit with the start. There's some arguments you could make, but we'll start there. This is the conventional wisdom of where computing started with ENIAC. Manchester Baby was in 48. I couldn't find any good pictures, so it doesn't get any pictures. And then Ed Sack was in 49. And then we're going to skip ahead a bit to the PDP 11, which is what's sort of interesting for us, because the PDP 11 is where we really started developing Unix. The actual first version was PDP 7, but this is where we really started to have Unix as we know it, and that's what I'm going to focus on. So one little point in this computer architecture history that's worth noting is in 85 we got the, we got the I386. And this was the point where consumer hardware at reasonable prices could conceivably run a Unix system without some serious compromises. So now I'm going to give you a little refresher on how process address space works, because that's what we're going to be talking about. In an old Unix program, traditional Unix program, you have a big process address space, and the kernel maps the program into memory. You have some code, you have some data, you have BSS, which is a bunch of things that start out as zeros. So all those global variables that were uninitialized, they start as zeros. And then you have a bit of unmapped stuff at the beginning, at least you hope it's unmapped, because it's the null pointer. So when you dereference the null pointer, we want to fault to not have interesting things happen. You have the stack, conventionally you put the stack up at the top of the process. The stack grows down. It goes that way. Then you have the heap. That's the stuff above BSS. And the heap grows up. Now ideally, they don't meet in the middle. But the heap is all your dynamic memory allocations that isn't your program stack. Now we are going to take a look at how that maps into the physical address space. So these different sections get mapped into the physical address space in different places. It doesn't really matter where they go. We have paging mechanisms, so we can use physical address space efficiently. Some of these things, like the code and data, are backed by disk. And then some of those are mapped copy on write, so that when you write to them in your program, so you change the data in your global variables, or change your global variables, you don't write that back to disk. And musically, we are now heading into the world where we do this on purpose, because that's persistent memory. So we are heading back into what happens if you screw up and don't implement copy on write. Now think about the, in the context of this address space, we have two things that we track. So as I said, you don't want the heap and the stack to meet in the middle and run into each other. So we manage the break, which is the top of the heap, traditionally. And then we have the stack, the stack pointer. We manage that. So now, let's get back to UNIX history. So first, the very, very first bit of UNIX was set 1970-ish in PDP 7. We don't have public documentation of any of that. We start with V1. We see the system, the sys break sys call, first appears, or at least is first documented. It's there. However, V1, the V1 dump doesn't have any documentation, so you can read the code, see what it does. But there's no explanation as to how you ought to use it or whatnot. V2, about the same, except it was renamed to break. You might notice at that time, it was the break function. So you might notice we're probably not running C yet, because break is a keyword in C. So we're there. V3, in 1973, we finally get some documentation. So we get a man page, which says that break sets the system's idea of the highest location used by the program to adder, the argument. Locations greater than adder and below the stack pointer are not swapped and thus are thus liable for unexpected modification. You notice at this point that we're using virtual memory not for protection at all. In fact, as far as I can tell, what we're using it for is to make process-swapping context switching cheaper by not having to change the page mappings for the rest of the pages. At least, that's what I infer. And in an extremely minimal system, this is a sensible approach, assuming you don't want fault tolerance or anything like that. So back to the history. V4, the system call has now been renamed to S-break. And the SBRK library call is introduced. So again, break sets the system's idea of the lowest location not used by the program to adder. So it says the same thing as before except backwards. Rounded up to the next multiple of 64 bytes, which I don't believe SBRK does in modern UNIX. And it's interesting to me that it's 64 bytes because words were smaller then. So I'm wondering what the motivation for that particular rounding choice was on the PDP11. But I haven't found out. Sir? That was the granularity of the segmentation register. Ah, that makes sense. This is why I'm glad that I have old timers in the audience. You can correct me on my talk. Quite pleasing. So locations not less than adder and below the stack pointer are not in the address space and thus will cause a memory violation in a fast sense. So now we're seeing actual protection from the virtual memory system. So continuing on through the manual, we see the manual for SBRK, which is the C interface to the break command. The SBRK command takes an increment, which is positive or negative, and moves the break and then returns a pointer to that location. So Inker adds more bytes to the program's data space and a pointer is returned to the start of the new area. Another bit. When a program begins execute, another snippet I found that I thought was kind of interesting. When a program begins execution by exec, the break is set to the highest location defined by the program. So that's the end of BSS and the data storage area. So that's the end of BSS. Ordinarily therefore, only programs with growing data areas need to use break. I read this and I sort of giggled myself. I was like, programs that don't use dynamic memory allocation, that's really weird. And I said this in one I gave this talk before, at BSTTW, and one of my co-presenters pointed out he works in high performance computing. And in high performance computing, that's the norm. You statically define the size of all your giant arrays, you recompile when you want a new array. And that's the world that was there and that's the world today. In fact, there's a bunch of good reasons for that in HPC because that means you have static sized loops and you can unroll them without any limit. Don't forget that we were on 16, but you should use right there. There wasn't a lot of memory to allocate in the first place. Absolutely. So I probably had too many Fs in my address space diagram, even with the dots. Okay. So here we are back. Here's where SBRK was introduced again. So in 75v4 introduced break, which is another interface to the same thing, just another software interface. And then in 1983, 4.4 BST documents a map that does not implement it. And the whole family of interfaces. And we'll get to what those interfaces are. But first, let's look at some problems with the break interface. So things that don't work real well. So one problem is heap fragmentation. So with break, you keep incrementing, incrementing, incrementing, you're allocating some memory. And you decide this huge thing that you've allocated previously, you don't want that anymore. We can't give it back to the curl. Now you have to do bookkeeping so you can remember that you can reuse it. So that's not great. On a 16-bit machine, you're probably very carefully doing that bookkeeping, possibly hard coded. But in this case, once you start to see 32-bit and 64-bit machines, this becomes problematic. You have to do a bunch of work. Another issue is that you'd like to have memory sharing. So let's consider an LS program. This is a statically linked LS program mapped into physical address space. We start another one. We should be able to share the code. And we should be able to share the data, or part of the data, the read-only part of the data. And then we can't share the BSS, we can't share the heap, and we can't share the stack, which makes sense. We can do this with a statically linked program with SBRK because the kernel does these mappings. So it can make sure that it shares the pages. But when we get to dynamic linking, we've got some new problems. Now, in a dynamically linked program, the kernel initially maps the stack, the program, and the runtime linker. The runtime linker is then started, and it maps libc. And libc, of course, the proportions here are probably exactly opposite for your average program. Libc is a bloated beast, and cat has far more arguments than it should, but nonetheless is small, or LS even is pretty small. So you'd like to have sharing there, but if you were using SBRK to allocate some space, opening libc and reading it and then splatting it into memory, you wouldn't have any sharing. And you could do ridiculous things, but you're not going to do ridiculous memory deduplication here. So that's another problem. So you've got your heap here again. So then let's consider multi-threaded programs. You have a new way to create heap fragmentation. You spawn a thread with SBRK, you give it a stack. Oh, now we need some more heap. You know, some more heap. That's not what you want, especially because when your threads exit, then you've got these little stack bits left in there that you would need to reclaim. Instead, you'd really like your stack to be off somewhere else with some nice guard pages around it, so when you walk off the end, things go boom instead of something else. So that's some of the problems that I feel probably motivated the M-Map interface. That's all back-formed, but that's things that are why you don't just want SBRK. So let's talk about the M-Map interface as documented in 4.2 BSD. So we have M-Map, of course. It allocates address space and alters backing mappings. We have M-Unmap, which removes backings. We have M-Map was documented. BSD is, as far as I know, none of them have ever implemented it. Lennox does implement it. It has all the perils of realloc, except with page management. And it is typically, so it's interesting. It's not the worst idea, but it's really easy to screw up realloc. So it would be good to know, it would be good to study how they're using it. So there are some usage models that are very useful and that are safe and manageable. And there are other ones that I find unlikely people would get right. And in particular, once you add Cherry, which I'll talk about in a bit to the mix, it gets quite complicated. I think it is all doable. The question is, are you adding so much complexity? Well, are you adding interfaces that are easy to get wrong? And M-Map is easy enough to screw up. We have the memory M-Protect. M-Protect alters the permissions on pages. So you can, for instance, create a writable page and then make it executable later if you're using a JIT compiler, things like that. M-Advise provides usage hints to the kernel and also for reasons that I have not quite figured out. There's also M-Advise Free, which unmapped pages effectively, which is effectively an unmapped, remapped operation. And probably shouldn't have been in there, but that arrived at some point. M-Incore gives you a one character per page status of what's the state of a given page for a range. And then SBRK, of course, was documented, and SSTK, which is like SBRK, but for moving the stack down. Now in Forged 2 BSD, SBRK was implemented. Interestingly, SSTK, as far as I can tell, is another one of those things that was never implemented. I think I did just recently shoot it in for BSD. The empty implementation. So, yeah, that was a fun one. Well, there was the stub implementation always. The stub implementation changed quite a lot over time, including getting an MP Safe Marker. But one of those things about code debt. So here we are, back to the first references. And then in 1990, 4.3 Reno had M-Map as implemented from Mach. And I don't know when the actual, well, I think I looked up when the actual commit was, but didn't write it down here. But one of the things that was, I found interesting when I was doing all this sponking, which was mostly in the Unix history repo. Is that the wisdom I had gotten from just talking to people was I thought that M-Map came from Mach. But the documentation is before any Mach release. And the Mach interfaces are totally different and kind of weird. So I'm curious what the actual history was there. Yeah, yeah, yeah, because I knew, yeah, I knew we had taken their stuff. But I had somehow absorbed this idea that we got M-Map from Mach, but it's in fact, we got the implementation from Mach, but not the actual interface. So a few more points along the scale before I go and start tearing down M-Map a bit. So in 2003, OpenBSD implemented WXRX. So the idea that no page should ever be both writable and executable. So this is a good thing. Prevents you from splatting shell code straight into a, you know, straight onto your stack and then running it, ideally. All that good stuff. So there are some issues with WXRX. There's some things you have to solve. So one of them is that with a just-in-time compiler, you need a writable page, but you can't have it both writable and executable. So you need some writable space. You need to, so generally what you do is you map something writable and then you remove writ and add exec, this leads to an interesting thing in the OpenBSD implementation. Because there's no way to express what the maximum permissions are on a page or what the maximum permissions you should allow on a page, every page is allowed to become executable. You have to make a system call to do it with them and call mProtect, but exec is always added to the MaxProt permissions, which is a bit suboptimal. But it's because mMap can't express this concept. So how do you do Jets? So you turn that feature off in something that Jets. Yeah. That makes sense. So there's that. And then one more that's relevant to the rest of my discussion is that in 2012, the project that I've been working on since then kicked off, I think we wrote proposals in, well, we other people wrote proposals in 2010. But Cherry changes the way we do pointers. So in Cherry, pointers have bounds and permissions associated with them. They're a bit bigger. Architecturally, they look like they contain 256 bits of data, more or less. In practice, they're 128 bits in memory. So we double the size of pointers. But for that, we get strong bounds and we get permissions on pointers. So you can have load store permissions and you have exec permissions. And then we have strong monotonicity guarantees on manipulating pointers, which is to say that if I have a pointer that has just right permission on it, just store permission, I cannot add load permission to it. I cannot manipulate it to create a capability pointer with load permission. Now, so you need to make your decisions early. So we'd like to do WXRX on pointers, but Mmap returns a pointer and there's no way to get a new pointer when you decide to toggle from read-write to execute only or read execute more likely. So some API changes are required to handle this situation if you want to do this. One option you could take here is that you could let M protect return a pointer, which could then, when you give you a pointer with the new permissions you created, that would be one way to go. Or you might need some other mechanism. So that's a place where cherry requires that we make some changes here. There's also some Mmap functionality issues. So Mmap just manages the virtual address space as this open, expensive thing. It takes integer arguments, including that pointer hint. That's just an integer. And it conflates address reservation and mapping of stuff behind it. The lack of boundaries on reservation is what gives us things like stack clash because you create a stack and from that reference to your stack, you can just keep going and you can jump into another stack. You can do math on those things. So cherry would help you, but it's also you can make math errors and think you're manipulating inside that reservation you made and really be off somewhere else in the address space doing stuff and making a mess of things. There's also some lack of expressiveness in the interface. So for instance, there's no portable way to express alignment of things. So if you want more, well, you get page alignment no matter what. But if you say wanted super page alignment, FreeBSD has a flag, but there's no portable way to say I want something super page aligned or I want something, I don't know, a megabyte aligned or something if for some hardware reason you need that. There's also no way, as I alluded to before, to express a maximum permissions on a mapping, which you would like to do, I feel. So another problem with that map, too many damn arguments. How many people can just sit down and write them all down in order? Right. Many people can. Many of the best programmers I know are like, nope, I read the manual. If I haven't been writing M-Map calls all day, I'm reading the manual. And then many calls don't use all of them. So you have to get them all right and then you have to not screw it up. And then we have way too many failure modes. So FreeBSD 11.1 had 19 documented errors, 14 of which were E-inval or 15 of which were E-inval. So if the kernel says no, then what did I do wrong? What's going on? And then we made it worse. We introduced MapGuard. That added, I think another four documented E-invales and I think it's actually considerably worse than that because there is one giant if statement of if this and this and this but MapGuard no blah or, you know, but not this and that and what things. Four lines long. And it's all just, yeah, if any of this happens, E-inval. In Archery, I got so fed up with this, I added a new K-Trace probe, which is sysericaws, an inserted code and broke up all the if statements. And so I splat ASCII strings into the log and say, you did, it happened this way because your pointer permissions were this and this was expected. So there's more ways to fail, but I wrote them out. I have not fully updated the latest one and I've not tried to upstream that, but, you know, that's a problem we have here. Some other M-Map issues. There's no support for mapping more pages than requested. What I mean by that is if you were using, for instance, non-transparent superpages and you wanted to map something that's like one page short of the superpage size and it's a file, you know, you might want to just map a superpage size thing and fill it in. You know, there's good reasons for our design, but you might want to do things like that. Also in Cherry, as I alluded, we have 256 bits of data in 128 bits and the way we do that is we compress our bounds. So at larger sizes, the granularity of your bounds goes up from byte granularity to, you know, one, a little bit at a time. And so if you allocate more than a gigabyte of memory in one go in the current design, then, you know, if you allocate two gigabytes of memory or something in between one and two gigabytes of memory, your granularity is two pages now. And so the kernel either would have to do all sorts of shenanigans to reserve that page and not give it up to somebody else, the extra page, or demand that you do it. Or it could round it up if we had a way to do that. But there's no sense of interface to say, actually, I did this. Ironically, this is something that for all of the horror that is System 5 shared memory, they got this right. There's a handle to your allocation. You free the whole thing at once. And there's no... And so it can be whatever size it wants, as long as it's as big as you asked for. And I alluded to it previously. There's no concept of ownership in the address space. So if you make a reservation, you get your math wrong, you could be stomping on some other stack. So that's not good. You know, I would like to say I want to reserve some space and I want to put some things in it. And if I try to put some things outside of it, then I clearly didn't mean to do that. So let's not support that. So there are some non-portable solutions to some things. So John Baldwin, so we got the aligned super flag, which is, you know, give me something super page aligned because I know it's going to be bigger than super pages. Or in the case of RTLD, we just figure whatever, a little fragmentation doesn't hurt. And we actually super page aligned all libraries. And also map aligned allows arbitrary power of two alignment. And those are, they're flags you wore into the flags. So that's nice. It works well. It's non-portable though. And then coming soon, we're planning to bring in an additional set of protection flags. There's a MaxProt macro inside of which you put the protections you want to be, you want to be the maximum protections and or that with your other protections. And we'll be able to set MaxProt. So these are non-portable ways we can deal with some of these problems. And we want to do this to bring, to help us bring WXRX into the tree. Because in most cases, it's a one line change to a program. Say, oh, you know, that, you know, Beehive, for instance, maps, maps prop none, the address space of the VM. And then loads things into it with protections. Well, if we just make a little tweak there and say, yeah, let's, let's map that with a MaxProt, with the MaxProt of RWX, because that's what it needs. But we can still map it prop none. We don't have to worry about sort of increasing the permissions on the pointer if the pointer were a cherry pointer. So now I have sort of an RFC for a new interface. It solves a bunch of the problems we have and solves some of these problems I've alluded to. So the new interface, the first part of it is CM reserve. C started as capability, now it's cookie, because cookies are good. And my goal here is to have an interface which is, which provides benefit even without capability, capability memory management or capability memory protection or without other pointer integrity schemes, which is the reason I designed it. But the goal is to have benefits for everyone. So CM reserve reserves some address space. It takes a reservation object, which I'll get into in a bit, a length, because obviously you're reserving some address space, a hint, which is the fixed address that you want to map at potentially. Protection, including maximum protection. And then returns a request object. Returns a, yeah, and takes a request object. Once you get a successful reservation, you can then get a pointer to it. And the reason we separate getting a pointer to it from making the reservation is that in the cherry world, I want to be able to get a read write pointer and a write execute pointer or a read execute pointer separately. And I don't ever want user space to have both. We have discussed, but I think no one is, no one has enough guts to do a hardware implementation where there are no read write execute pointers. But that is something you could do. You could literally mean there is never one and you can't manufacture one no matter what you do. So, but we'd like to support that use case. Next, there's CM map, because one of the common things you do with M map is you map in part of a library, you map in a library and then you map in the BSS at the end as a bunch of anonymous pages. So you need to be able to take your reservation and manipulate the mappings underneath it. We have a close, which is say get rid of the handle we've created, which means now you can't manipulate it anymore. So if you wanted immutable page mappings, this will give you immutable page mappings. So you have to exit if you want to get rid of these. We have a concept of a CM restrict, which is there's a bunch of operations you could perform. We might want to leave the handle open, but only let you unmap. So that you can't monkey around with permissions anymore, for instance. ID of a stat function. Idea here is to allow introspection at a level, at a more interesting level than that provided by MINCOR. So the information is there, for instance, to tell you what object maps, what objects are mapped into a reservation. So we'd like to be able to query that. There are some interesting challenges here, because obviously if you do this wrong, you can break ASLR by enumerating through the handles. So you don't want that, but we have ideas on how to fix that. And then the other M-advise, MINCOR, M-inherit, M-sync, M-unmap, all those would be just the same as before, except that they only operate on a single reservation or on regions within that. So a little bit more on map requests. My idea is to map, is to have map requests follow the model of pthread-adderty. So you have a request object. It's an opaque thing. You initialize it. You make some manipulations to it. You set, you know, which file you want on it and whatnot. And then using accessors, and then you pass it on to M-reserve or to CM-map. And the goal is to have useful defaults, so ideally you do as little as possible. So if you just want some empty pages like Meloc does, it should be no more than like two calls. And so little on Unixy, but you know, Aposix does it. And my hope is that it will be less error-prone than the mess that is CM-map. Now, a couple of cherry extensions. So in addition to the C get pointer that we had before, I've added a C get cap so I can retrieve a capability pointer, not just a virtual address. It also, C end perms, which allows you to restrict the set of permissions on future pointers returned by C get cap. Because there's a default set of permissions that any mapping gets that would be dictated by the max plot, but there are other permissions that normally we would give to capabilities that are created by the kernel for user space. And you might say, yeah, I don't want those, for whatever reason. So that's my proposal. So independent of my proposal, what do people think? Is it time for something new? Nope? No, all right. I'm still feeling we should go back to using braces. Part of the, it seems to me that part of what you're running into here is the fact that someone, we've raised everything as a back, so just kind of extending it. Yes? I guess. Yeah, that was not something I guess, I don't think I have access. Which is it in, is the 286 stuff in the Unix history repo? Yeah, I mean, I glossed over it in that I knew there were things, but there were more compromises there. So I think there are less of an, things without an MMU or more. Yeah. So my current proposal does, is about address based management. So it doesn't do that. You could conceive of a proposal where you say, I want another mapping to the stuff behind this mapping, so a new handle, and do that. But the goal of the proposal is that in, so in Cherry, pointers have permissions, fundamentally. So I could have, I could have, you know, you would do the thing where you make writable pages, write to them, and then turn them executable. And then similarly you would, but because we don't want you to ever have a pointer that's capable of both reading and writing, you need a way to get two pointers. So that's the reason for the C get cap. See I'm get cap. Sean. So I like, I like a lot of the work that Cherry is doing. In fact, all of it, it seems this type of interface is just a game of double XR support. And there's more here, play, right, you're doing Cherry stuff as well. But just for WXORX support, TurnedBSD has shown that we don't need to do that. You know, we have a more strict implementation of WXORX than what OpenBSD has, because we follow what we have in common. You know, I think not only do, if we were to replace NMAP, we also have to convince the rest of the world to follow our work. Absolutely. And Capsicum has shown that we're not really all that successful. Well, so part of the goal here is you should be able to implement NMAP on top of this. And in fact, there's nothing stopping you from doing a poor implementation of this on top of NMAP. That's the goal and probably something we would do before we made a proposal. So that there is an adoption path that, you know, works on shady Android phones that never get updates. But, you know, we are talking to people who maintain other operating systems. I was just going to comment that if you implemented NMAP on top of this then... Kirk. So, yeah, I turned that off in Cherry. I fail... So, in my adaptation of JML to Cherry, I just make all the map fixed requests fail. Because I know that's what they're trying to do. And you can't glue two capabilities together. We don't provide a facility to do that. We could. But that's a very significant... I mean, there's no reason that you couldn't have a sys call that says, so I have these two capabilities, please glue them together and give me a new one. But that definitely is non-monotonic behavior. So you have to be very careful. So we may... That's something we've not explored because it's turned out we haven't really needed to do it. I think it does have some impacts in JMLOCK in particular because JMLOCK has made some decisions about small buckets that mean there are really bizarre performance cliffs. If you slightly increasing the size of a data structure can cause you to go into the next bucket and then allocate seven times as many pages or do seven times as many M maps for the same number of small allocations because you go from a seven-page bucket to a one-page bucket. And that minimizes absolute fragmentation at the cost, at considerable performance cost in some cases. Eric? Three concerns that we have all been implementing for the times particularly garbage collected. First is being able to take an anonymous mapping and sort of retarget to a file. So say all these pages are now this range of files, subjects of restrictions. Second is efficiently flip pages back and forth between right and left executable. Third is some manner of call interface. To be able to say, okay, kick me back here if this page is not present or tell me when pages are about to be kicked, the benefits to garbage collection particularly about a matter of substantial. All right. Speaking of garbage collection, have you looked into the Unoxys user-ford-fd interface? No. User-ford-fd is manipulating mapped areas so that you can be notified when this page is written or wrote to. Additionally, people especially garbage collectors did that by putting a sanitation board handler on the screen. So the garbage collector language people didn't do that much but now the virtual machine live migration people also want the same functionality. So in Unox they made the center phase which was kind of Byzantine or whatever you want to call it. And your API would actually absorb what they are trying to do. Interesting. We'll have to look at that. We do have somebody actually looking actively at garbage collection and looking at a non-reuse model. Look at the paper. It will be sold but Matthew Berks and Henry Berger look at working garbage collection. I think that's an individual. But that discusses and a call. I mean, the benefits are quite substantial. So I mean, just to those, of course, your systems work and if you've seen the dude paper out of Stanford but they have a way in the garbage collection tricks that you want at much lower cost than you could do some other mechanism. But my question was I guess, I think I really like the direction for this work in general. I was wondering also what you had in thought for NUMA and stuff like that given, especially that we're hitting the limit of number of cores per socket. That would be, well, it's not something I've really thought about much but the request object format should I think help us give us a place to have more than just our current 32 flags. So more things we can ask for. And I think that would be something to explore before anyone tried to standardize something. I definitely agree. I actually got this on the route map for 13 but the ability to mark reasons in user space is non-catchable or more generally. Yeah. So we have a little time so I'll give you a little bit more here. So another point in history in 2016, we decided as an experiment to ship ARM64 and RISC-5 without SBRK. Mostly it turns out it's used for incorrect attempts to measure heap use. I fixed the documentation so it says those don't work but it's still there. Some of them require some force to disable. There's also some internal allocators. The funnest one I think was probably all the GNU binutils crap tries really hard to find a way to use the RISC-5. So if the symbol is there, but it's fine if there's no symbol. Actually, I don't think it will call system itself but it's fine if you don't declare it. It'll just look for it and use it. It doesn't need it but it won't sit anyway. It's very important. And then some Lisp interpreters. Mostly unpopular ones. But we did win the editor war because we broke Emacs. So, oops. Turns out, so Emacs did finally, this year, did finally implement an SBRK-less implementation. They decided to join the 80s. So it's very good. Andy? Yes, they did call us Matt. But, you know. We said, you know, it's been documented since 83, guess. And SBRK has been deprecated since the early 90s. So, you know, now Emacs worked without SBRK. I'm planning to finish killing these silly things off in FreeBSD 13 because it's time. If you really need it, there's plenty of ways you could do a peer user space implementation. And really, all you need to do is allocate more BSS and have a big symbol. And for most uses, that'll just work. So that's all I've got. Thank you for coming. I'm happy to take any more questions if you do have any. Yes? Well, I just wanted to reinforce if you are doing this, I would really like to give this info that's in my anyway integrated with the user phone. Because it's really annoying that people like me currently use segmentation for this kind of thing. Because building, just building the segment context is so expensive. It's a reputation that they do is like a few orders of magnitude cheaper. And you have a much easier time getting the experience, not just the page, but probably the world. That would be a really good thing. Yes. We have people who are actively working on garbage collections, I will send them this and say they should implement it in FreeBSD so they can test it. And they're good, so they should do a good job. I think we should do that regardless of what happens to an M-Map alternative. For SBRK, we could. I'm a little worried that if I put the linker warnings in, I will break ports too much. I mean, you can always ignore the deprecated warnings. So I could try, I could do that if you think that'd be appropriate. Oh yeah. Did you test the two multiple and see which one breaks? Well, Ed was pushing me to do an X-bronze, so we'll get that done soon. I know a new one popped up recently, which is why the documentation was updated. Because I broke something. It was again some old interpreted language. Thank you everyone.
 Okay, it's 1.30, so I'm going to go ahead and get started.  I'm here to, well, my title is, is it time to replace Mmap?  But it's really, my talk is really a history of virtual memory management, virtual address  based management.  And I give a proposal for the future that solves some of the problems we have today and some  of the problems that the project I'm working on is creating.  So let's see if that's any better.  There, okay, there's some pickup.  Yeah.  Okay, is that picking up?  No, does not seem to be.  Audio level.  Okay.  Okay, is that picking up at all?  It's on.  It's on, yeah.  Okay.  I think, well, I can.  Okay, let's try that then.  Okay, is that more useful?  Okay, so we're talking about what, I'm going to talk today about what we usually talk,  call memory, but in fact what I'm talking about is virtual address space management.  And that's a process of both allocating virtual address space and putting something behind  it so that it doesn't give you a page fault because there's nothing there when you do  it.  But first we're going to, so we're going to start with some history.  Here we see a timeline of a little bit of the future and the entirety of computing history.  You know, you could, you could quibble a bit with the start.  There's some arguments you could make, but we'll start there.  This is the conventional wisdom of where computing started with ENIAC.  Manchester Baby was in 48.  I couldn't find any good pictures, so it doesn't get any pictures.  And then Ed Sack was in 49.  And then we're going to skip ahead a bit to the PDP 11, which is what's sort of interesting  for us, because the PDP 11 is where we really started developing Unix.  The actual first version was PDP 7, but this is where we really started to have Unix as  we know it, and that's what I'm going to focus on.  So one little point in this computer architecture history that's worth noting is in 85 we got  the, we got the I386.  And this was the point where consumer hardware at reasonable prices could conceivably run  a Unix system without some serious compromises.  So now I'm going to give you a little refresher on how process address space works, because  that's what we're going to be talking about.  In an old Unix program, traditional Unix program, you have a big process address space, and  the kernel maps the program into memory.  You have some code, you have some data, you have BSS, which is a bunch of things that  start out as zeros.  So all those global variables that were uninitialized, they start as zeros.  And then you have a bit of unmapped stuff at the beginning, at least you hope it's unmapped,  because it's the null pointer.  So when you dereference the null pointer, we want to fault to not have interesting things  happen.  You have the stack, conventionally you put the stack up at the top of the process.  The stack grows down.  It goes that way.  Then you have the heap.  That's the stuff above BSS.  And the heap grows up.  Now ideally, they don't meet in the middle.  But the heap is all your dynamic memory allocations that isn't your program stack.  Now we are going to take a look at how that maps into the physical address space.  So these different sections get mapped into the physical address space in different places.  It doesn't really matter where they go.  We have paging mechanisms, so we can use physical address space efficiently.  Some of these things, like the code and data, are backed by disk.  And then some of those are mapped copy on write, so that when you write to them in your  program, so you change the data in your global variables, or change your global variables,  you don't write that back to disk.  And musically, we are now heading into the world where we do this on purpose, because  that's persistent memory.  So we are heading back into what happens if you screw up and don't implement copy on write.  Now think about the, in the context of this address space, we have two things that we  track.  So as I said, you don't want the heap and the stack to meet in the middle and run into  each other.  So we manage the break, which is the top of the heap, traditionally.  And then we have the stack, the stack pointer.  We manage that.  So now, let's get back to UNIX history.  So first, the very, very first bit of UNIX was set 1970-ish in PDP 7.  We don't have public documentation of any of that.  We start with V1.  We see the system, the sys break sys call, first appears, or at least is first documented.  It's there.  However, V1, the V1 dump doesn't have any documentation, so you can read the code, see  what it does.  But there's no explanation as to how you ought to use it or whatnot.  V2, about the same, except it was renamed to break.  You might notice at that time, it was the break function.  So you might notice we're probably not running C yet, because break is a keyword in C.  So we're there.  V3, in 1973, we finally get some documentation.  So we get a man page, which says that break sets the system's idea of the highest location  used by the program to adder, the argument.  Locations greater than adder and below the stack pointer are not swapped and thus are  thus liable for unexpected modification.  You notice at this point that we're using virtual memory not for protection at all.  In fact, as far as I can tell, what we're using it for is to make process-swapping context  switching cheaper by not having to change the page mappings for the rest of the pages.  At least, that's what I infer.  And in an extremely minimal system, this is a sensible approach, assuming you don't want  fault tolerance or anything like that.  So back to the history.  V4, the system call has now been renamed to S-break.  And the SBRK library call is introduced.  So again, break sets the system's idea of the lowest location not used by the program  to adder.  So it says the same thing as before except backwards.  Rounded up to the next multiple of 64 bytes, which I don't believe SBRK does in modern  UNIX.  And it's interesting to me that it's 64 bytes because words were smaller then.  So I'm wondering what the motivation for that particular rounding choice was on the  PDP11.  But I haven't found out.  Sir?  That was the granularity of the segmentation register.  Ah, that makes sense.  This is why I'm glad that I have old timers in the audience.  You can correct me on my talk.  Quite pleasing.  So locations not less than adder and below the stack pointer are not in the address space  and thus will cause a memory violation in a fast sense.  So now we're seeing actual protection from the virtual memory system.  So continuing on through the manual, we see the manual for SBRK, which is the C interface  to the break command.  The SBRK command takes an increment, which is positive or negative, and moves the break  and then returns a pointer to that location.  So Inker adds more bytes to the program's data space and a pointer is returned to the  start of the new area.  Another bit.  When a program begins execute, another snippet I found that I thought was kind of interesting.  When a program begins execution by exec, the break is set to the highest location defined  by the program.  So that's the end of BSS and the data storage area.  So that's the end of BSS.  Ordinarily therefore, only programs with growing data areas need to use break.  I read this and I sort of giggled myself.  I was like, programs that don't use dynamic memory allocation, that's really weird.  And I said this in one I gave this talk before, at BSTTW, and one of my co-presenters pointed  out he works in high performance computing.  And in high performance computing, that's the norm.  You statically define the size of all your giant arrays, you recompile when you want a  new array.  And that's the world that was there and that's the world today.  In fact, there's a bunch of good reasons for that in HPC because that means you have static  sized loops and you can unroll them without any limit.  Don't forget that we were on 16, but you should use right there.  There wasn't a lot of memory to allocate in the first place.  Absolutely.  So I probably had too many Fs in my address space diagram, even with the dots.  Okay.  So here we are back.  Here's where SBRK was introduced again.  So in 75v4 introduced break, which is another interface to the same thing, just another  software interface.  And then in 1983, 4.4 BST documents a map that does not implement it.  And the whole family of interfaces.  And we'll get to what those interfaces are.  But first, let's look at some problems with the break interface.  So things that don't work real well.  So one problem is heap fragmentation.  So with break, you keep incrementing, incrementing, incrementing, you're allocating some memory.  And you decide this huge thing that you've allocated previously, you don't want that  anymore.  We can't give it back to the curl.  Now you have to do bookkeeping so you can remember that you can reuse it.  So that's not great.  On a 16-bit machine, you're probably very carefully doing that bookkeeping, possibly hard coded.  But in this case, once you start to see 32-bit and 64-bit machines, this becomes problematic.  You have to do a bunch of work.  Another issue is that you'd like to have memory sharing.  So let's consider an LS program.  This is a statically linked LS program mapped into physical address space.  We start another one.  We should be able to share the code.  And we should be able to share the data, or part of the data, the read-only part of the  data.  And then we can't share the BSS, we can't share the heap, and we can't share the stack,  which makes sense.  We can do this with a statically linked program with SBRK because the kernel does these mappings.  So it can make sure that it shares the pages.  But when we get to dynamic linking, we've got some new problems.  Now, in a dynamically linked program, the kernel initially maps the stack, the program,  and the runtime linker.  The runtime linker is then started, and it maps libc.  And libc, of course, the proportions here are probably exactly opposite for your average  program.  Libc is a bloated beast, and cat has far more arguments than it should, but nonetheless  is small, or LS even is pretty small.  So you'd like to have sharing there, but if you were using SBRK to allocate some space,  opening libc and reading it and then splatting it into memory, you wouldn't have any sharing.  And you could do ridiculous things, but you're not going to do ridiculous memory deduplication  here.  So that's another problem.  So you've got your heap here again.  So then let's consider multi-threaded programs.  You have a new way to create heap fragmentation.  You spawn a thread with SBRK, you give it a stack.  Oh, now we need some more heap.  You know, some more heap.  That's not what you want, especially because when your threads exit, then you've got these  little stack bits left in there that you would need to reclaim.  Instead, you'd really like your stack to be off somewhere else with some nice guard pages  around it, so when you walk off the end, things go boom instead of something else.  So that's some of the problems that I feel probably motivated the M-Map interface.  That's all back-formed, but that's things that are why you don't just want SBRK.  So let's talk about the M-Map interface as documented in 4.2 BSD.  So we have M-Map, of course.  It allocates address space and alters backing mappings.  We have M-Unmap, which removes backings.  We have M-Map was documented.  BSD is, as far as I know, none of them have ever implemented it.  Lennox does implement it.  It has all the perils of realloc, except with page management.  And it is typically, so it's interesting.  It's not the worst idea, but it's really easy to screw up realloc.  So it would be good to know, it would be good to study how they're using it.  So there are some usage models that are very useful and that are safe and manageable.  And there are other ones that I find unlikely people would get right.  And in particular, once you add Cherry, which I'll talk about in a bit to the mix, it gets  quite complicated.  I think it is all doable.  The question is, are you adding so much complexity?  Well, are you adding interfaces that are easy to get wrong?  And M-Map is easy enough to screw up.  We have the memory M-Protect.  M-Protect alters the permissions on pages.  So you can, for instance, create a writable page and then make it executable later if  you're using a JIT compiler, things like that.  M-Advise provides usage hints to the kernel and also for reasons that I have not quite  figured out.  There's also M-Advise Free, which unmapped pages effectively, which is effectively an  unmapped, remapped operation.  And probably shouldn't have been in there, but that arrived at some point.  M-Incore gives you a one character per page status of what's the state of a given page  for a range.  And then SBRK, of course, was documented, and SSTK, which is like SBRK, but for moving  the stack down.  Now in Forged 2 BSD, SBRK was implemented.  Interestingly, SSTK, as far as I can tell, is another one of those things that was never  implemented.  I think I did just recently shoot it in for BSD.  The empty implementation.  So, yeah, that was a fun one.  Well, there was the stub implementation always.  The stub implementation changed quite a lot over time, including getting an MP Safe Marker.  But one of those things about code debt.  So here we are, back to the first references.  And then in 1990, 4.3 Reno had M-Map as implemented from Mach.  And I don't know when the actual, well, I think I looked up when the actual commit was,  but didn't write it down here.  But one of the things that was, I found interesting when I was doing all this sponking, which was  mostly in the Unix history repo.  Is that the wisdom I had gotten from just talking to people was I thought that M-Map  came from Mach.  But the documentation is before any Mach release.  And the Mach interfaces are totally different and kind of weird.  So I'm curious what the actual history was there.  Yeah, yeah, yeah, because I knew, yeah, I knew we had taken their stuff.  But I had somehow absorbed this idea that we got M-Map from Mach, but it's in fact,  we got the implementation from Mach, but not the actual interface.  So a few more points along the scale before I go and start tearing down M-Map a bit.  So in 2003, OpenBSD implemented WXRX.  So the idea that no page should ever be both writable and executable.  So this is a good thing.  Prevents you from splatting shell code straight into a, you know, straight onto your stack  and then running it, ideally.  All that good stuff.  So there are some issues with WXRX.  There's some things you have to solve.  So one of them is that with a just-in-time compiler, you need a writable page, but you  can't have it both writable and executable.  So you need some writable space.  You need to, so generally what you do is you map something writable and then you remove  writ and add exec, this leads to an interesting thing in the OpenBSD implementation.  Because there's no way to express what the maximum permissions are on a page or what  the maximum permissions you should allow on a page, every page is allowed to become executable.  You have to make a system call to do it with them and call mProtect, but exec is always  added to the MaxProt permissions, which is a bit suboptimal.  But it's because mMap can't express this concept.  So how do you do Jets?  So you turn that feature off in something that Jets.  Yeah.  That makes sense.  So there's that.  And then one more that's relevant to the rest of my discussion is that in 2012, the project  that I've been working on since then kicked off, I think we wrote proposals in, well,  we other people wrote proposals in 2010.  But Cherry changes the way we do pointers.  So in Cherry, pointers have bounds and permissions associated with them.  They're a bit bigger.  Architecturally, they look like they contain 256 bits of data, more or less.  In practice, they're 128 bits in memory.  So we double the size of pointers.  But for that, we get strong bounds and we get permissions on pointers.  So you can have load store permissions and you have exec permissions.  And then we have strong monotonicity guarantees on manipulating pointers, which is to say  that if I have a pointer that has just right permission on it, just store permission, I  cannot add load permission to it.  I cannot manipulate it to create a capability pointer with load permission.  Now, so you need to make your decisions early.  So we'd like to do WXRX on pointers, but Mmap returns a pointer and there's no way  to get a new pointer when you decide to toggle from read-write to execute only or read execute  more likely.  So some API changes are required to handle this situation if you want to do this.  One option you could take here is that you could let M protect return a pointer, which  could then, when you give you a pointer with the new permissions you created, that would  be one way to go.  Or you might need some other mechanism.  So that's a place where cherry requires that we make some changes here.  There's also some Mmap functionality issues.  So Mmap just manages the virtual address space as this open, expensive thing.  It takes integer arguments, including that pointer hint.  That's just an integer.  And it conflates address reservation and mapping of stuff behind it.  The lack of boundaries on reservation is what gives us things like stack clash because you  create a stack and from that reference to your stack, you can just keep going and you  can jump into another stack.  You can do math on those things.  So cherry would help you, but it's also you can make math errors and think you're manipulating  inside that reservation you made and really be off somewhere else in the address space  doing stuff and making a mess of things.  There's also some lack of expressiveness in the interface.  So for instance, there's no portable way to express alignment of things.  So if you want more, well, you get page alignment no matter what.  But if you say wanted super page alignment, FreeBSD has a flag, but there's no portable  way to say I want something super page aligned or I want something, I don't know, a megabyte  aligned or something if for some hardware reason you need that.  There's also no way, as I alluded to before, to express a maximum permissions on a mapping,  which you would like to do, I feel.  So another problem with that map, too many damn arguments.  How many people can just sit down and write them all down in order?  Right.  Many people can.  Many of the best programmers I know are like, nope, I read the manual.  If I haven't been writing M-Map calls all day, I'm reading the manual.  And then many calls don't use all of them.  So you have to get them all right and then you have to not screw it up.  And then we have way too many failure modes.  So FreeBSD 11.1 had 19 documented errors, 14 of which were E-inval or 15 of which were  E-inval.  So if the kernel says no, then what did I do wrong?  What's going on?  And then we made it worse.  We introduced MapGuard.  That added, I think another four documented E-invales and I think it's actually considerably  worse than that because there is one giant if statement of if this and this and this  but MapGuard no blah or, you know, but not this and that and what things.  Four lines long.  And it's all just, yeah, if any of this happens, E-inval.  In Archery, I got so fed up with this, I added a new K-Trace probe, which is sysericaws,  an inserted code and broke up all the if statements.  And so I splat ASCII strings into the log and say, you did, it happened this way because  your pointer permissions were this and this was expected.  So there's more ways to fail, but I wrote them out.  I have not fully updated the latest one and I've not tried to upstream that, but, you  know, that's a problem we have here.  Some other M-Map issues.  There's no support for mapping more pages than requested.  What I mean by that is if you were using, for instance, non-transparent superpages and  you wanted to map something that's like one page short of the superpage size and it's  a file, you know, you might want to just map a superpage size thing and fill it in.  You know, there's good reasons for our design, but you might want to do things like that.  Also in Cherry, as I alluded, we have 256 bits of data in 128 bits and the way we do that  is we compress our bounds.  So at larger sizes, the granularity of your bounds goes up from byte granularity to, you  know, one, a little bit at a time.  And so if you allocate more than a gigabyte of memory in one go in the current design,  then, you know, if you allocate two gigabytes of memory or something in between one and  two gigabytes of memory, your granularity is two pages now.  And so the kernel either would have to do all sorts of shenanigans to reserve that page  and not give it up to somebody else, the extra page, or demand that you do it.  Or it could round it up if we had a way to do that.  But there's no sense of interface to say, actually, I did this.  Ironically, this is something that for all of the horror that is System 5 shared memory,  they got this right.  There's a handle to your allocation.  You free the whole thing at once.  And there's no...  And so it can be whatever size it wants, as long as it's as big as you asked for.  And I alluded to it previously.  There's no concept of ownership in the address space.  So if you make a reservation, you get your math wrong, you could be stomping on some  other stack.  So that's not good.  You know, I would like to say I want to reserve some space and I want to put some things in  it.  And if I try to put some things outside of it, then I clearly didn't mean to do that.  So let's not support that.  So there are some non-portable solutions to some things.  So John Baldwin, so we got the aligned super flag, which is, you know, give me something  super page aligned because I know it's going to be bigger than super pages.  Or in the case of RTLD, we just figure whatever, a little fragmentation doesn't hurt.  And we actually super page aligned all libraries.  And also map aligned allows arbitrary power of two alignment.  And those are, they're flags you wore into the flags.  So that's nice.  It works well.  It's non-portable though.  And then coming soon, we're planning to bring in an additional set of protection flags.  There's a MaxProt macro inside of which you put the protections you want to be, you want  to be the maximum protections and or that with your other protections.  And we'll be able to set MaxProt.  So these are non-portable ways we can deal with some of these problems.  And we want to do this to bring, to help us bring WXRX into the tree.  Because in most cases, it's a one line change to a program.  Say, oh, you know, that, you know, Beehive, for instance, maps, maps prop none, the address  space of the VM.  And then loads things into it with protections.  Well, if we just make a little tweak there and say, yeah, let's, let's map that with  a MaxProt, with the MaxProt of RWX, because that's what it needs.  But we can still map it prop none.  We don't have to worry about sort of increasing the permissions on the pointer if the pointer  were a cherry pointer.  So now I have sort of an RFC for a new interface.  It solves a bunch of the problems we have and solves some of these problems I've alluded  to.  So the new interface, the first part of it is CM reserve.  C started as capability, now it's cookie, because cookies are good.  And my goal here is to have an interface which is, which provides benefit even without capability,  capability memory management or capability memory protection or without other pointer  integrity schemes, which is the reason I designed it.  But the goal is to have benefits for everyone.  So CM reserve reserves some address space.  It takes a reservation object, which I'll get into in a bit, a length, because obviously  you're reserving some address space, a hint, which is the fixed address that you want to  map at potentially.  Protection, including maximum protection.  And then returns a request object.  Returns a, yeah, and takes a request object.  Once you get a successful reservation, you can then get a pointer to it.  And the reason we separate getting a pointer to it from making the reservation is that  in the cherry world, I want to be able to get a read write pointer and a write execute  pointer or a read execute pointer separately.  And I don't ever want user space to have both.  We have discussed, but I think no one is, no one has enough guts to do a hardware implementation  where there are no read write execute pointers.  But that is something you could do.  You could literally mean there is never one and you can't manufacture one no matter what  you do.  So, but we'd like to support that use case.  Next, there's CM map, because one of the common things you do with M map is you map in part  of a library, you map in a library and then you map in the BSS at the end as a bunch of  anonymous pages.  So you need to be able to take your reservation and manipulate the mappings underneath it.  We have a close, which is say get rid of the handle we've created, which means now you  can't manipulate it anymore.  So if you wanted immutable page mappings, this will give you immutable page mappings.  So you have to exit if you want to get rid of these.  We have a concept of a CM restrict, which is there's a bunch of operations you could  perform.  We might want to leave the handle open, but only let you unmap.  So that you can't monkey around with permissions anymore, for instance.  ID of a stat function.  Idea here is to allow introspection at a level, at a more interesting level than that provided  by MINCOR.  So the information is there, for instance, to tell you what object maps, what objects  are mapped into a reservation.  So we'd like to be able to query that.  There are some interesting challenges here, because obviously if you do this wrong, you  can break ASLR by enumerating through the handles.  So you don't want that, but we have ideas on how to fix that.  And then the other M-advise, MINCOR, M-inherit, M-sync, M-unmap, all those would be just  the same as before, except that they only operate on a single reservation or on regions  within that.  So a little bit more on map requests.  My idea is to map, is to have map requests follow the model of pthread-adderty.  So you have a request object.  It's an opaque thing.  You initialize it.  You make some manipulations to it.  You set, you know, which file you want on it and whatnot.  And then using accessors, and then you pass it on to M-reserve or to CM-map.  And the goal is to have useful defaults, so ideally you do as little as possible.  So if you just want some empty pages like Meloc does, it should be no more than like  two calls.  And so little on Unixy, but you know, Aposix does it.  And my hope is that it will be less error-prone than the mess that is CM-map.  Now, a couple of cherry extensions.  So in addition to the C get pointer that we had before, I've added a C get cap so I can  retrieve a capability pointer, not just a virtual address.  It also, C end perms, which allows you to restrict the set of permissions on future  pointers returned by C get cap.  Because there's a default set of permissions that any mapping gets that would be dictated  by the max plot, but there are other permissions that normally we would give to capabilities  that are created by the kernel for user space.  And you might say, yeah, I don't want those, for whatever reason.  So that's my proposal.  So independent of my proposal, what do people think?  Is it time for something new?  Nope?  No, all right.  I'm still feeling we should go back to using braces.  Part of the, it seems to me that part of what you're running into here is the fact that  someone, we've raised everything as a back, so just kind of extending it.  Yes?  I guess.  Yeah, that was not something I guess, I don't think I have access.  Which is it in, is the 286 stuff in the Unix history repo?  Yeah, I mean, I glossed over it in that I knew there were things, but there were more  compromises there.  So I think there are less of an, things without an MMU or more.  Yeah.  So my current proposal does, is about address based management.  So it doesn't do that.  You could conceive of a proposal where you say, I want another mapping to the stuff behind  this mapping, so a new handle, and do that.  But the goal of the proposal is that in, so in Cherry, pointers have permissions, fundamentally.  So I could have, I could have, you know, you would do the thing where you make writable  pages, write to them, and then turn them executable.  And then similarly you would, but because we don't want you to ever have a pointer that's  capable of both reading and writing, you need a way to get two pointers.  So that's the reason for the C get cap.  See I'm get cap.  Sean.  So I like, I like a lot of the work that Cherry is doing.  In fact, all of it, it seems this type of interface is just a game of double XR support.  And there's more here, play, right, you're doing Cherry stuff as well.  But just for WXORX support, TurnedBSD has shown that we don't need to do that.  You know, we have a more strict implementation of WXORX than what OpenBSD has, because we  follow what we have in common.  You know, I think not only do, if we were to replace NMAP, we also have to convince the  rest of the world to follow our work.  Absolutely.  And Capsicum has shown that we're not really all that successful.  Well, so part of the goal here is you should be able to implement NMAP on top of this.  And in fact, there's nothing stopping you from doing a poor implementation of this on  top of NMAP.  That's the goal and probably something we would do before we made a proposal.  So that there is an adoption path that, you know, works on shady Android phones that  never get updates.  But, you know, we are talking to people who maintain other operating systems.  I was just going to comment that if you implemented NMAP on top of this then...  Kirk.  So, yeah, I turned that off in Cherry.  I fail...  So, in my adaptation of JML to Cherry, I just make all the map fixed requests fail.  Because I know that's what they're trying to do.  And you can't glue two capabilities together.  We don't provide a facility to do that.  We could.  But that's a very significant...  I mean, there's no reason that you couldn't have a sys call that says, so I have these  two capabilities, please glue them together and give me a new one.  But that definitely is non-monotonic behavior.  So you have to be very careful.  So we may...  That's something we've not explored because it's turned out we haven't really needed to  do it.  I think it does have some impacts in JMLOCK in particular because JMLOCK has made some  decisions about small buckets that mean there are really bizarre performance cliffs.  If you slightly increasing the size of a data structure can cause you to go into the next  bucket and then allocate seven times as many pages or do seven times as many M maps for  the same number of small allocations because you go from a seven-page bucket to a one-page  bucket.  And that minimizes absolute fragmentation at the cost, at considerable performance cost  in some cases.  Eric?  Three concerns that we have all been implementing for the times particularly garbage collected.  First is being able to take an anonymous mapping and sort of retarget to a file.  So say all these pages are now this range of files, subjects of restrictions.  Second is efficiently flip pages back and forth between right and left executable.  Third is some manner of call interface.  To be able to say, okay, kick me back here if this page is not present or tell me when  pages are about to be kicked, the benefits to garbage collection particularly about a  matter of substantial.  All right.  Speaking of garbage collection, have you looked into the Unoxys user-ford-fd interface?  No.  User-ford-fd is manipulating mapped areas so that you can be notified when this page  is written or wrote to.  Additionally, people especially garbage collectors did that by putting a sanitation board handler  on the screen.  So the garbage collector language people didn't do that much but now the virtual machine live  migration people also want the same functionality.  So in Unox they made the center phase which was kind of Byzantine or whatever you want  to call it.  And your API would actually absorb what they are trying to do.  Interesting.  We'll have to look at that.  We do have somebody actually looking actively at garbage collection and looking at a non-reuse  model.  Look at the paper.  It will be sold but Matthew Berks and Henry Berger look at working garbage collection.  I think that's an individual.  But that discusses and a call.  I mean, the benefits are quite substantial.  So I mean, just to those, of course, your systems work and if you've seen the dude paper  out of Stanford but they have a way in the garbage collection tricks that you want at  much lower cost than you could do some other mechanism.  But my question was I guess, I think I really like the direction for this work in general.  I was wondering also what you had in thought for NUMA and stuff like that given, especially  that we're hitting the limit of number of cores per socket.  That would be, well, it's not something I've really thought about much but the request  object format should I think help us give us a place to have more than just our current  32 flags.  So more things we can ask for.  And I think that would be something to explore before anyone tried to standardize something.  I definitely agree.  I actually got this on the route map for 13 but the ability to mark reasons in user space  is non-catchable or more generally.  Yeah.  So we have a little time so I'll give you a little bit more here.  So another point in history in 2016, we decided as an experiment to ship ARM64 and RISC-5  without SBRK.  Mostly it turns out it's used for incorrect attempts to measure heap use.  I fixed the documentation so it says those don't work but it's still there.  Some of them require some force to disable.  There's also some internal allocators.  The funnest one I think was probably all the GNU binutils crap tries really hard to find  a way to use the RISC-5.  So if the symbol is there, but it's fine if there's no symbol.  Actually, I don't think it will call system itself but it's fine if you don't declare  it.  It'll just look for it and use it.  It doesn't need it but it won't sit anyway.  It's very important.  And then some Lisp interpreters.  Mostly unpopular ones.  But we did win the editor war because we broke Emacs.  So, oops.  Turns out, so Emacs did finally, this year, did finally implement an SBRK-less implementation.  They decided to join the 80s.  So it's very good.  Andy?  Yes, they did call us Matt.  But, you know.  We said, you know, it's been documented since 83, guess.  And SBRK has been deprecated since the early 90s.  So, you know, now Emacs worked without SBRK.  I'm planning to finish killing these silly things off in FreeBSD 13 because it's time.  If you really need it, there's plenty of ways you could do a peer user space implementation.  And really, all you need to do is allocate more BSS and have a big symbol.  And for most uses, that'll just work.  So that's all I've got.  Thank you for coming.  I'm happy to take any more questions if you do have any.  Yes?  Well, I just wanted to reinforce if you are doing this, I would really like to give this info that's in my anyway integrated with the user phone.  Because it's really annoying that people like me currently use segmentation for this kind of thing.  Because building, just building the segment context is so expensive.  It's a reputation that they do is like a few orders of magnitude cheaper.  And you have a much easier time getting the experience, not just the page, but probably the world.  That would be a really good thing.  Yes.  We have people who are actively working on garbage collections, I will send them this and say they should implement it in FreeBSD so they can test it.  And they're good, so they should do a good job.  I think we should do that regardless of what happens to an M-Map alternative.  For SBRK, we could. I'm a little worried that if I put the linker warnings in, I will break ports too much.  I mean, you can always ignore the deprecated warnings.  So I could try, I could do that if you think that'd be appropriate.  Oh yeah.  Did you test the two multiple and see which one breaks?  Well, Ed was pushing me to do an X-bronze, so we'll get that done soon.  I know a new one popped up recently, which is why the documentation was updated.  Because I broke something.  It was again some old interpreted language.  Thank you everyone.
Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_0_107.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_108_1259.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_1260_2711.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_2712_3359.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_3360_5087.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_5088_5519.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_5520_5987.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_5988_9011.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_9012_10511.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_10512_11939.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_11940_12551.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_12552_15011.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_15012_15611.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_15612_16307.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_16308_18863.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_18864_19715.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_19716_20363.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_20364_20975.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_20976_27155.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_27156_27299.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_27300_28247.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_28248_29375.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_29376_30479.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_30480_31679.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_31680_32351.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_32352_32471.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_32472_33815.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_33816_34019.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_34020_34091.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_34092_37211.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_37212_37535.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_37536_37931.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_37932_38783.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_38784_38879.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_38880_41255.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_41256_41423.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_41424_41471.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_41472_41615.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_41616_41963.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_41964_42107.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_42108_42443.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_42444_43967.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_43968_44531.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_44532_46787.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_46788_47507.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_47508_47903.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_47904_48215.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_48216_49007.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_49008_50147.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_50148_56435.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_56436_56603.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_56604_57395.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_57396_59711.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_59712_62327.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_62328_62375.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_62376_63275.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_63276_64007.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_64008_65363.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_65364_68543.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_68544_68711.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_68712_71051.png Brooks_Davis__Is_it_time_to_replace_mmap_--_BSDCan_2018_nRJWS9_cEUU_71052_71646.png
Okay, it's 1.30, so I'm going to go ahead and get started. I'm here to, well, my title is, is it time to replace Mmap? But it's really, my talk is really a history of virtual memory management, virtual address based management. And I give a proposal for the future that solves some of the problems we have today and some of the problems that the project I'm working on is creating. So let's see if that's any better. There, okay, there's some pickup. Yeah. Okay, is that picking up? No, does not seem to be. Audio level. Okay. Okay, is that picking up at all? It's on. It's on, yeah. Okay. I think, well, I can. Okay, let's try that then. Okay, is that more useful? Okay, so we're talking about what, I'm going to talk today about what we usually talk, call memory, but in fact what I'm talking about is virtual address space management. And that's a process of both allocating virtual address space and putting something behind it so that it doesn't give you a page fault because there's nothing there when you do it. But first we're going to, so we're going to start with some history. Here we see a timeline of a little bit of the future and the entirety of computing history. You know, you could, you could quibble a bit with the start. There's some arguments you could make, but we'll start there. This is the conventional wisdom of where computing started with ENIAC. Manchester Baby was in 48. I couldn't find any good pictures, so it doesn't get any pictures. And then Ed Sack was in 49. And then we're going to skip ahead a bit to the PDP 11, which is what's sort of interesting for us, because the PDP 11 is where we really started developing Unix. The actual first version was PDP 7, but this is where we really started to have Unix as we know it, and that's what I'm going to focus on. So one little point in this computer architecture history that's worth noting is in 85 we got the, we got the I386. And this was the point where consumer hardware at reasonable prices could conceivably run a Unix system without some serious compromises. So now I'm going to give you a little refresher on how process address space works, because that's what we're going to be talking about. In an old Unix program, traditional Unix program, you have a big process address space, and the kernel maps the program into memory. You have some code, you have some data, you have BSS, which is a bunch of things that start out as zeros. So all those global variables that were uninitialized, they start as zeros. And then you have a bit of unmapped stuff at the beginning, at least you hope it's unmapped, because it's the null pointer. So when you dereference the null pointer, we want to fault to not have interesting things happen. You have the stack, conventionally you put the stack up at the top of the process. The stack grows down. It goes that way. Then you have the heap. That's the stuff above BSS. And the heap grows up. Now ideally, they don't meet in the middle. But the heap is all your dynamic memory allocations that isn't your program stack. Now we are going to take a look at how that maps into the physical address space. So these different sections get mapped into the physical address space in different places. It doesn't really matter where they go. We have paging mechanisms, so we can use physical address space efficiently. Some of these things, like the code and data, are backed by disk. And then some of those are mapped copy on write, so that when you write to them in your program, so you change the data in your global variables, or change your global variables, you don't write that back to disk. And musically, we are now heading into the world where we do this on purpose, because that's persistent memory. So we are heading back into what happens if you screw up and don't implement copy on write. Now think about the, in the context of this address space, we have two things that we track. So as I said, you don't want the heap and the stack to meet in the middle and run into each other. So we manage the break, which is the top of the heap, traditionally. And then we have the stack, the stack pointer. We manage that. So now, let's get back to UNIX history. So first, the very, very first bit of UNIX was set 1970-ish in PDP 7. We don't have public documentation of any of that. We start with V1. We see the system, the sys break sys call, first appears, or at least is first documented. It's there. However, V1, the V1 dump doesn't have any documentation, so you can read the code, see what it does. But there's no explanation as to how you ought to use it or whatnot. V2, about the same, except it was renamed to break. You might notice at that time, it was the break function. So you might notice we're probably not running C yet, because break is a keyword in C. So we're there. V3, in 1973, we finally get some documentation. So we get a man page, which says that break sets the system's idea of the highest location used by the program to adder, the argument. Locations greater than adder and below the stack pointer are not swapped and thus are thus liable for unexpected modification. You notice at this point that we're using virtual memory not for protection at all. In fact, as far as I can tell, what we're using it for is to make process-swapping context switching cheaper by not having to change the page mappings for the rest of the pages. At least, that's what I infer. And in an extremely minimal system, this is a sensible approach, assuming you don't want fault tolerance or anything like that. So back to the history. V4, the system call has now been renamed to S-break. And the SBRK library call is introduced. So again, break sets the system's idea of the lowest location not used by the program to adder. So it says the same thing as before except backwards. Rounded up to the next multiple of 64 bytes, which I don't believe SBRK does in modern UNIX. And it's interesting to me that it's 64 bytes because words were smaller then. So I'm wondering what the motivation for that particular rounding choice was on the PDP11. But I haven't found out. Sir? That was the granularity of the segmentation register. Ah, that makes sense. This is why I'm glad that I have old timers in the audience. You can correct me on my talk. Quite pleasing. So locations not less than adder and below the stack pointer are not in the address space and thus will cause a memory violation in a fast sense. So now we're seeing actual protection from the virtual memory system. So continuing on through the manual, we see the manual for SBRK, which is the C interface to the break command. The SBRK command takes an increment, which is positive or negative, and moves the break and then returns a pointer to that location. So Inker adds more bytes to the program's data space and a pointer is returned to the start of the new area. Another bit. When a program begins execute, another snippet I found that I thought was kind of interesting. When a program begins execution by exec, the break is set to the highest location defined by the program. So that's the end of BSS and the data storage area. So that's the end of BSS. Ordinarily therefore, only programs with growing data areas need to use break. I read this and I sort of giggled myself. I was like, programs that don't use dynamic memory allocation, that's really weird. And I said this in one I gave this talk before, at BSTTW, and one of my co-presenters pointed out he works in high performance computing. And in high performance computing, that's the norm. You statically define the size of all your giant arrays, you recompile when you want a new array. And that's the world that was there and that's the world today. In fact, there's a bunch of good reasons for that in HPC because that means you have static sized loops and you can unroll them without any limit. Don't forget that we were on 16, but you should use right there. There wasn't a lot of memory to allocate in the first place. Absolutely. So I probably had too many Fs in my address space diagram, even with the dots. Okay. So here we are back. Here's where SBRK was introduced again. So in 75v4 introduced break, which is another interface to the same thing, just another software interface. And then in 1983, 4.4 BST documents a map that does not implement it. And the whole family of interfaces. And we'll get to what those interfaces are. But first, let's look at some problems with the break interface. So things that don't work real well. So one problem is heap fragmentation. So with break, you keep incrementing, incrementing, incrementing, you're allocating some memory. And you decide this huge thing that you've allocated previously, you don't want that anymore. We can't give it back to the curl. Now you have to do bookkeeping so you can remember that you can reuse it. So that's not great. On a 16-bit machine, you're probably very carefully doing that bookkeeping, possibly hard coded. But in this case, once you start to see 32-bit and 64-bit machines, this becomes problematic. You have to do a bunch of work. Another issue is that you'd like to have memory sharing. So let's consider an LS program. This is a statically linked LS program mapped into physical address space. We start another one. We should be able to share the code. And we should be able to share the data, or part of the data, the read-only part of the data. And then we can't share the BSS, we can't share the heap, and we can't share the stack, which makes sense. We can do this with a statically linked program with SBRK because the kernel does these mappings. So it can make sure that it shares the pages. But when we get to dynamic linking, we've got some new problems. Now, in a dynamically linked program, the kernel initially maps the stack, the program, and the runtime linker. The runtime linker is then started, and it maps libc. And libc, of course, the proportions here are probably exactly opposite for your average program. Libc is a bloated beast, and cat has far more arguments than it should, but nonetheless is small, or LS even is pretty small. So you'd like to have sharing there, but if you were using SBRK to allocate some space, opening libc and reading it and then splatting it into memory, you wouldn't have any sharing. And you could do ridiculous things, but you're not going to do ridiculous memory deduplication here. So that's another problem. So you've got your heap here again. So then let's consider multi-threaded programs. You have a new way to create heap fragmentation. You spawn a thread with SBRK, you give it a stack. Oh, now we need some more heap. You know, some more heap. That's not what you want, especially because when your threads exit, then you've got these little stack bits left in there that you would need to reclaim. Instead, you'd really like your stack to be off somewhere else with some nice guard pages around it, so when you walk off the end, things go boom instead of something else. So that's some of the problems that I feel probably motivated the M-Map interface. That's all back-formed, but that's things that are why you don't just want SBRK. So let's talk about the M-Map interface as documented in 4.2 BSD. So we have M-Map, of course. It allocates address space and alters backing mappings. We have M-Unmap, which removes backings. We have M-Map was documented. BSD is, as far as I know, none of them have ever implemented it. Lennox does implement it. It has all the perils of realloc, except with page management. And it is typically, so it's interesting. It's not the worst idea, but it's really easy to screw up realloc. So it would be good to know, it would be good to study how they're using it. So there are some usage models that are very useful and that are safe and manageable. And there are other ones that I find unlikely people would get right. And in particular, once you add Cherry, which I'll talk about in a bit to the mix, it gets quite complicated. I think it is all doable. The question is, are you adding so much complexity? Well, are you adding interfaces that are easy to get wrong? And M-Map is easy enough to screw up. We have the memory M-Protect. M-Protect alters the permissions on pages. So you can, for instance, create a writable page and then make it executable later if you're using a JIT compiler, things like that. M-Advise provides usage hints to the kernel and also for reasons that I have not quite figured out. There's also M-Advise Free, which unmapped pages effectively, which is effectively an unmapped, remapped operation. And probably shouldn't have been in there, but that arrived at some point. M-Incore gives you a one character per page status of what's the state of a given page for a range. And then SBRK, of course, was documented, and SSTK, which is like SBRK, but for moving the stack down. Now in Forged 2 BSD, SBRK was implemented. Interestingly, SSTK, as far as I can tell, is another one of those things that was never implemented. I think I did just recently shoot it in for BSD. The empty implementation. So, yeah, that was a fun one. Well, there was the stub implementation always. The stub implementation changed quite a lot over time, including getting an MP Safe Marker. But one of those things about code debt. So here we are, back to the first references. And then in 1990, 4.3 Reno had M-Map as implemented from Mach. And I don't know when the actual, well, I think I looked up when the actual commit was, but didn't write it down here. But one of the things that was, I found interesting when I was doing all this sponking, which was mostly in the Unix history repo. Is that the wisdom I had gotten from just talking to people was I thought that M-Map came from Mach. But the documentation is before any Mach release. And the Mach interfaces are totally different and kind of weird. So I'm curious what the actual history was there. Yeah, yeah, yeah, because I knew, yeah, I knew we had taken their stuff. But I had somehow absorbed this idea that we got M-Map from Mach, but it's in fact, we got the implementation from Mach, but not the actual interface. So a few more points along the scale before I go and start tearing down M-Map a bit. So in 2003, OpenBSD implemented WXRX. So the idea that no page should ever be both writable and executable. So this is a good thing. Prevents you from splatting shell code straight into a, you know, straight onto your stack and then running it, ideally. All that good stuff. So there are some issues with WXRX. There's some things you have to solve. So one of them is that with a just-in-time compiler, you need a writable page, but you can't have it both writable and executable. So you need some writable space. You need to, so generally what you do is you map something writable and then you remove writ and add exec, this leads to an interesting thing in the OpenBSD implementation. Because there's no way to express what the maximum permissions are on a page or what the maximum permissions you should allow on a page, every page is allowed to become executable. You have to make a system call to do it with them and call mProtect, but exec is always added to the MaxProt permissions, which is a bit suboptimal. But it's because mMap can't express this concept. So how do you do Jets? So you turn that feature off in something that Jets. Yeah. That makes sense. So there's that. And then one more that's relevant to the rest of my discussion is that in 2012, the project that I've been working on since then kicked off, I think we wrote proposals in, well, we other people wrote proposals in 2010. But Cherry changes the way we do pointers. So in Cherry, pointers have bounds and permissions associated with them. They're a bit bigger. Architecturally, they look like they contain 256 bits of data, more or less. In practice, they're 128 bits in memory. So we double the size of pointers. But for that, we get strong bounds and we get permissions on pointers. So you can have load store permissions and you have exec permissions. And then we have strong monotonicity guarantees on manipulating pointers, which is to say that if I have a pointer that has just right permission on it, just store permission, I cannot add load permission to it. I cannot manipulate it to create a capability pointer with load permission. Now, so you need to make your decisions early. So we'd like to do WXRX on pointers, but Mmap returns a pointer and there's no way to get a new pointer when you decide to toggle from read-write to execute only or read execute more likely. So some API changes are required to handle this situation if you want to do this. One option you could take here is that you could let M protect return a pointer, which could then, when you give you a pointer with the new permissions you created, that would be one way to go. Or you might need some other mechanism. So that's a place where cherry requires that we make some changes here. There's also some Mmap functionality issues. So Mmap just manages the virtual address space as this open, expensive thing. It takes integer arguments, including that pointer hint. That's just an integer. And it conflates address reservation and mapping of stuff behind it. The lack of boundaries on reservation is what gives us things like stack clash because you create a stack and from that reference to your stack, you can just keep going and you can jump into another stack. You can do math on those things. So cherry would help you, but it's also you can make math errors and think you're manipulating inside that reservation you made and really be off somewhere else in the address space doing stuff and making a mess of things. There's also some lack of expressiveness in the interface. So for instance, there's no portable way to express alignment of things. So if you want more, well, you get page alignment no matter what. But if you say wanted super page alignment, FreeBSD has a flag, but there's no portable way to say I want something super page aligned or I want something, I don't know, a megabyte aligned or something if for some hardware reason you need that. There's also no way, as I alluded to before, to express a maximum permissions on a mapping, which you would like to do, I feel. So another problem with that map, too many damn arguments. How many people can just sit down and write them all down in order? Right. Many people can. Many of the best programmers I know are like, nope, I read the manual. If I haven't been writing M-Map calls all day, I'm reading the manual. And then many calls don't use all of them. So you have to get them all right and then you have to not screw it up. And then we have way too many failure modes. So FreeBSD 11.1 had 19 documented errors, 14 of which were E-inval or 15 of which were E-inval. So if the kernel says no, then what did I do wrong? What's going on? And then we made it worse. We introduced MapGuard. That added, I think another four documented E-invales and I think it's actually considerably worse than that because there is one giant if statement of if this and this and this but MapGuard no blah or, you know, but not this and that and what things. Four lines long. And it's all just, yeah, if any of this happens, E-inval. In Archery, I got so fed up with this, I added a new K-Trace probe, which is sysericaws, an inserted code and broke up all the if statements. And so I splat ASCII strings into the log and say, you did, it happened this way because your pointer permissions were this and this was expected. So there's more ways to fail, but I wrote them out. I have not fully updated the latest one and I've not tried to upstream that, but, you know, that's a problem we have here. Some other M-Map issues. There's no support for mapping more pages than requested. What I mean by that is if you were using, for instance, non-transparent superpages and you wanted to map something that's like one page short of the superpage size and it's a file, you know, you might want to just map a superpage size thing and fill it in. You know, there's good reasons for our design, but you might want to do things like that. Also in Cherry, as I alluded, we have 256 bits of data in 128 bits and the way we do that is we compress our bounds. So at larger sizes, the granularity of your bounds goes up from byte granularity to, you know, one, a little bit at a time. And so if you allocate more than a gigabyte of memory in one go in the current design, then, you know, if you allocate two gigabytes of memory or something in between one and two gigabytes of memory, your granularity is two pages now. And so the kernel either would have to do all sorts of shenanigans to reserve that page and not give it up to somebody else, the extra page, or demand that you do it. Or it could round it up if we had a way to do that. But there's no sense of interface to say, actually, I did this. Ironically, this is something that for all of the horror that is System 5 shared memory, they got this right. There's a handle to your allocation. You free the whole thing at once. And there's no... And so it can be whatever size it wants, as long as it's as big as you asked for. And I alluded to it previously. There's no concept of ownership in the address space. So if you make a reservation, you get your math wrong, you could be stomping on some other stack. So that's not good. You know, I would like to say I want to reserve some space and I want to put some things in it. And if I try to put some things outside of it, then I clearly didn't mean to do that. So let's not support that. So there are some non-portable solutions to some things. So John Baldwin, so we got the aligned super flag, which is, you know, give me something super page aligned because I know it's going to be bigger than super pages. Or in the case of RTLD, we just figure whatever, a little fragmentation doesn't hurt. And we actually super page aligned all libraries. And also map aligned allows arbitrary power of two alignment. And those are, they're flags you wore into the flags. So that's nice. It works well. It's non-portable though. And then coming soon, we're planning to bring in an additional set of protection flags. There's a MaxProt macro inside of which you put the protections you want to be, you want to be the maximum protections and or that with your other protections. And we'll be able to set MaxProt. So these are non-portable ways we can deal with some of these problems. And we want to do this to bring, to help us bring WXRX into the tree. Because in most cases, it's a one line change to a program. Say, oh, you know, that, you know, Beehive, for instance, maps, maps prop none, the address space of the VM. And then loads things into it with protections. Well, if we just make a little tweak there and say, yeah, let's, let's map that with a MaxProt, with the MaxProt of RWX, because that's what it needs. But we can still map it prop none. We don't have to worry about sort of increasing the permissions on the pointer if the pointer were a cherry pointer. So now I have sort of an RFC for a new interface. It solves a bunch of the problems we have and solves some of these problems I've alluded to. So the new interface, the first part of it is CM reserve. C started as capability, now it's cookie, because cookies are good. And my goal here is to have an interface which is, which provides benefit even without capability, capability memory management or capability memory protection or without other pointer integrity schemes, which is the reason I designed it. But the goal is to have benefits for everyone. So CM reserve reserves some address space. It takes a reservation object, which I'll get into in a bit, a length, because obviously you're reserving some address space, a hint, which is the fixed address that you want to map at potentially. Protection, including maximum protection. And then returns a request object. Returns a, yeah, and takes a request object. Once you get a successful reservation, you can then get a pointer to it. And the reason we separate getting a pointer to it from making the reservation is that in the cherry world, I want to be able to get a read write pointer and a write execute pointer or a read execute pointer separately. And I don't ever want user space to have both. We have discussed, but I think no one is, no one has enough guts to do a hardware implementation where there are no read write execute pointers. But that is something you could do. You could literally mean there is never one and you can't manufacture one no matter what you do. So, but we'd like to support that use case. Next, there's CM map, because one of the common things you do with M map is you map in part of a library, you map in a library and then you map in the BSS at the end as a bunch of anonymous pages. So you need to be able to take your reservation and manipulate the mappings underneath it. We have a close, which is say get rid of the handle we've created, which means now you can't manipulate it anymore. So if you wanted immutable page mappings, this will give you immutable page mappings. So you have to exit if you want to get rid of these. We have a concept of a CM restrict, which is there's a bunch of operations you could perform. We might want to leave the handle open, but only let you unmap. So that you can't monkey around with permissions anymore, for instance. ID of a stat function. Idea here is to allow introspection at a level, at a more interesting level than that provided by MINCOR. So the information is there, for instance, to tell you what object maps, what objects are mapped into a reservation. So we'd like to be able to query that. There are some interesting challenges here, because obviously if you do this wrong, you can break ASLR by enumerating through the handles. So you don't want that, but we have ideas on how to fix that. And then the other M-advise, MINCOR, M-inherit, M-sync, M-unmap, all those would be just the same as before, except that they only operate on a single reservation or on regions within that. So a little bit more on map requests. My idea is to map, is to have map requests follow the model of pthread-adderty. So you have a request object. It's an opaque thing. You initialize it. You make some manipulations to it. You set, you know, which file you want on it and whatnot. And then using accessors, and then you pass it on to M-reserve or to CM-map. And the goal is to have useful defaults, so ideally you do as little as possible. So if you just want some empty pages like Meloc does, it should be no more than like two calls. And so little on Unixy, but you know, Aposix does it. And my hope is that it will be less error-prone than the mess that is CM-map. Now, a couple of cherry extensions. So in addition to the C get pointer that we had before, I've added a C get cap so I can retrieve a capability pointer, not just a virtual address. It also, C end perms, which allows you to restrict the set of permissions on future pointers returned by C get cap. Because there's a default set of permissions that any mapping gets that would be dictated by the max plot, but there are other permissions that normally we would give to capabilities that are created by the kernel for user space. And you might say, yeah, I don't want those, for whatever reason. So that's my proposal. So independent of my proposal, what do people think? Is it time for something new? Nope? No, all right. I'm still feeling we should go back to using braces. Part of the, it seems to me that part of what you're running into here is the fact that someone, we've raised everything as a back, so just kind of extending it. Yes? I guess. Yeah, that was not something I guess, I don't think I have access. Which is it in, is the 286 stuff in the Unix history repo? Yeah, I mean, I glossed over it in that I knew there were things, but there were more compromises there. So I think there are less of an, things without an MMU or more. Yeah. So my current proposal does, is about address based management. So it doesn't do that. You could conceive of a proposal where you say, I want another mapping to the stuff behind this mapping, so a new handle, and do that. But the goal of the proposal is that in, so in Cherry, pointers have permissions, fundamentally. So I could have, I could have, you know, you would do the thing where you make writable pages, write to them, and then turn them executable. And then similarly you would, but because we don't want you to ever have a pointer that's capable of both reading and writing, you need a way to get two pointers. So that's the reason for the C get cap. See I'm get cap. Sean. So I like, I like a lot of the work that Cherry is doing. In fact, all of it, it seems this type of interface is just a game of double XR support. And there's more here, play, right, you're doing Cherry stuff as well. But just for WXORX support, TurnedBSD has shown that we don't need to do that. You know, we have a more strict implementation of WXORX than what OpenBSD has, because we follow what we have in common. You know, I think not only do, if we were to replace NMAP, we also have to convince the rest of the world to follow our work. Absolutely. And Capsicum has shown that we're not really all that successful. Well, so part of the goal here is you should be able to implement NMAP on top of this. And in fact, there's nothing stopping you from doing a poor implementation of this on top of NMAP. That's the goal and probably something we would do before we made a proposal. So that there is an adoption path that, you know, works on shady Android phones that never get updates. But, you know, we are talking to people who maintain other operating systems. I was just going to comment that if you implemented NMAP on top of this then... Kirk. So, yeah, I turned that off in Cherry. I fail... So, in my adaptation of JML to Cherry, I just make all the map fixed requests fail. Because I know that's what they're trying to do. And you can't glue two capabilities together. We don't provide a facility to do that. We could. But that's a very significant... I mean, there's no reason that you couldn't have a sys call that says, so I have these two capabilities, please glue them together and give me a new one. But that definitely is non-monotonic behavior. So you have to be very careful. So we may... That's something we've not explored because it's turned out we haven't really needed to do it. I think it does have some impacts in JMLOCK in particular because JMLOCK has made some decisions about small buckets that mean there are really bizarre performance cliffs. If you slightly increasing the size of a data structure can cause you to go into the next bucket and then allocate seven times as many pages or do seven times as many M maps for the same number of small allocations because you go from a seven-page bucket to a one-page bucket. And that minimizes absolute fragmentation at the cost, at considerable performance cost in some cases. Eric? Three concerns that we have all been implementing for the times particularly garbage collected. First is being able to take an anonymous mapping and sort of retarget to a file. So say all these pages are now this range of files, subjects of restrictions. Second is efficiently flip pages back and forth between right and left executable. Third is some manner of call interface. To be able to say, okay, kick me back here if this page is not present or tell me when pages are about to be kicked, the benefits to garbage collection particularly about a matter of substantial. All right. Speaking of garbage collection, have you looked into the Unoxys user-ford-fd interface? No. User-ford-fd is manipulating mapped areas so that you can be notified when this page is written or wrote to. Additionally, people especially garbage collectors did that by putting a sanitation board handler on the screen. So the garbage collector language people didn't do that much but now the virtual machine live migration people also want the same functionality. So in Unox they made the center phase which was kind of Byzantine or whatever you want to call it. And your API would actually absorb what they are trying to do. Interesting. We'll have to look at that. We do have somebody actually looking actively at garbage collection and looking at a non-reuse model. Look at the paper. It will be sold but Matthew Berks and Henry Berger look at working garbage collection. I think that's an individual. But that discusses and a call. I mean, the benefits are quite substantial. So I mean, just to those, of course, your systems work and if you've seen the dude paper out of Stanford but they have a way in the garbage collection tricks that you want at much lower cost than you could do some other mechanism. But my question was I guess, I think I really like the direction for this work in general. I was wondering also what you had in thought for NUMA and stuff like that given, especially that we're hitting the limit of number of cores per socket. That would be, well, it's not something I've really thought about much but the request object format should I think help us give us a place to have more than just our current 32 flags. So more things we can ask for. And I think that would be something to explore before anyone tried to standardize something. I definitely agree. I actually got this on the route map for 13 but the ability to mark reasons in user space is non-catchable or more generally. Yeah. So we have a little time so I'll give you a little bit more here. So another point in history in 2016, we decided as an experiment to ship ARM64 and RISC-5 without SBRK. Mostly it turns out it's used for incorrect attempts to measure heap use. I fixed the documentation so it says those don't work but it's still there. Some of them require some force to disable. There's also some internal allocators. The funnest one I think was probably all the GNU binutils crap tries really hard to find a way to use the RISC-5. So if the symbol is there, but it's fine if there's no symbol. Actually, I don't think it will call system itself but it's fine if you don't declare it. It'll just look for it and use it. It doesn't need it but it won't sit anyway. It's very important. And then some Lisp interpreters. Mostly unpopular ones. But we did win the editor war because we broke Emacs. So, oops. Turns out, so Emacs did finally, this year, did finally implement an SBRK-less implementation. They decided to join the 80s. So it's very good. Andy? Yes, they did call us Matt. But, you know. We said, you know, it's been documented since 83, guess. And SBRK has been deprecated since the early 90s. So, you know, now Emacs worked without SBRK. I'm planning to finish killing these silly things off in FreeBSD 13 because it's time. If you really need it, there's plenty of ways you could do a peer user space implementation. And really, all you need to do is allocate more BSS and have a big symbol. And for most uses, that'll just work. So that's all I've got. Thank you for coming. I'm happy to take any more questions if you do have any. Yes? Well, I just wanted to reinforce if you are doing this, I would really like to give this info that's in my anyway integrated with the user phone. Because it's really annoying that people like me currently use segmentation for this kind of thing. Because building, just building the segment context is so expensive. It's a reputation that they do is like a few orders of magnitude cheaper. And you have a much easier time getting the experience, not just the page, but probably the world. That would be a really good thing. Yes. We have people who are actively working on garbage collections, I will send them this and say they should implement it in FreeBSD so they can test it. And they're good, so they should do a good job. I think we should do that regardless of what happens to an M-Map alternative. For SBRK, we could. I'm a little worried that if I put the linker warnings in, I will break ports too much. I mean, you can always ignore the deprecated warnings. So I could try, I could do that if you think that'd be appropriate. Oh yeah. Did you test the two multiple and see which one breaks? Well, Ed was pushing me to do an X-bronze, so we'll get that done soon. I know a new one popped up recently, which is why the documentation was updated. Because I broke something. It was again some old interpreted language. Thank you everyone.
really a history of virtual memory management, have sort of an RFC for a new interface. It people think? Is it time for something new? Nope?