* [PATCH] Wasm support patch 1 (support systems without mmap) @ 2017-11-28 11:50 Nicholas Wilson 2017-11-28 15:46 ` Rich Felker 0 siblings, 1 reply; 4+ messages in thread From: Nicholas Wilson @ 2017-11-28 11:50 UTC (permalink / raw) To: musl I'm hoping the first patch is uncontroversial. WebAssembly has a linear/flat memory model, whereby it's simply impossible for the addressable memory to contain "holes". Therefore, mmap can't really be emulated, and all memory has to be allocated via brk. I've done this by allowing malloc to fall back to brk (even for allocations above MMAP_THRESHOLD) if mmap returns ENOSYS. It's one line of code that will do harm in "normal" systems, and allows platforms that are emulating syscalls to choose not to support mmap, and still get a working malloc if brk is working. All the best, Nick diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c index 9e05e1d6..572232e1 100644 --- a/src/malloc/malloc.c +++ b/src/malloc/malloc.c @@ -328,13 +328,17 @@ void *malloc(size_t n) size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE; char *base = __mmap(0, len, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); - if (base == (void *)-1) return 0; + if (base == MAP_FAILED) { + if (errno == ENOSYS) goto nommap; + return 0; + } c = (void *)(base + SIZE_ALIGN - OVERHEAD); c->csize = len - (SIZE_ALIGN - OVERHEAD); c->psize = SIZE_ALIGN - OVERHEAD; return CHUNK_TO_MEM(c); } +nommap: i = bin_index_up(n); for (;;) { uint64_t mask = mal.binmap & -(1ULL<<i); @@ -405,7 +409,7 @@ void *realloc(void *p, size_t n) newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE; if (oldlen == newlen) return p; base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE); - if (base == (void *)-1) + if (base == MAP_FAILED) goto copy_realloc; self = (void *)(base + extra); self->csize = newlen - extra; ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Wasm support patch 1 (support systems without mmap) 2017-11-28 11:50 [PATCH] Wasm support patch 1 (support systems without mmap) Nicholas Wilson @ 2017-11-28 15:46 ` Rich Felker 2017-11-28 16:34 ` Nicholas Wilson 0 siblings, 1 reply; 4+ messages in thread From: Rich Felker @ 2017-11-28 15:46 UTC (permalink / raw) To: musl On Tue, Nov 28, 2017 at 11:50:08AM +0000, Nicholas Wilson wrote: > I'm hoping the first patch is uncontroversial. > > WebAssembly has a linear/flat memory model, whereby it's simply > impossible for the addressable memory to contain "holes". Therefore, > mmap can't really be emulated, and all memory has to be allocated > via brk. This is not supported or supportable in musl's malloc. The heap that can be serviced by brk is only usable for allocation sizes less than ~128k. > I've done this by allowing malloc to fall back to brk (even for > allocations above MMAP_THRESHOLD) if mmap returns ENOSYS. > > It's one line of code that will do harm in "normal" systems, and > allows platforms that are emulating syscalls to choose not to > support mmap, and still get a working malloc if brk is working. The patch as written almost surely corrupts the heap structures or at least produces new heap expansion (no possibility of reuse) each time an allocation larger than ~128k is requested. This is because bin_index[_up] is not defined for n > MMAP_THRESHOLD. There are other places in musl that also depend on mmap working, like the TLS init code. brk on the other hand is only used as an optimization. I think what you should do, if it's hard to support both brk and mmap, is omit brk instead (have it return -ENOSYS), then have mmap always allocate lowest-available-page and keep some data structure (even just a bit array) representing which pages are free. This way you still keep everything in a contiguous range (possibly with some reusable gaps due to munmap) like you want. Rich > diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c > index 9e05e1d6..572232e1 100644 > --- a/src/malloc/malloc.c > +++ b/src/malloc/malloc.c > @@ -328,13 +328,17 @@ void *malloc(size_t n) > size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE; > char *base = __mmap(0, len, PROT_READ|PROT_WRITE, > MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); > - if (base == (void *)-1) return 0; > + if (base == MAP_FAILED) { > + if (errno == ENOSYS) goto nommap; > + return 0; > + } > c = (void *)(base + SIZE_ALIGN - OVERHEAD); > c->csize = len - (SIZE_ALIGN - OVERHEAD); > c->psize = SIZE_ALIGN - OVERHEAD; > return CHUNK_TO_MEM(c); > } > > +nommap: > i = bin_index_up(n); > for (;;) { > uint64_t mask = mal.binmap & -(1ULL<<i); > @@ -405,7 +409,7 @@ void *realloc(void *p, size_t n) > newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE; > if (oldlen == newlen) return p; > base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE); > - if (base == (void *)-1) > + if (base == MAP_FAILED) > goto copy_realloc; > self = (void *)(base + extra); > self->csize = newlen - extra; ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Wasm support patch 1 (support systems without mmap) 2017-11-28 15:46 ` Rich Felker @ 2017-11-28 16:34 ` Nicholas Wilson 2017-11-28 19:20 ` Rich Felker 0 siblings, 1 reply; 4+ messages in thread From: Nicholas Wilson @ 2017-11-28 16:34 UTC (permalink / raw) To: musl Oh, I'd missed that. Let's scrap this patch then, I'll post an updated version of Patch #3 (Wasm-specific files) that implements mmap using Wasm's underlying "brk" capability. I could use a bitmap to track free pages - but there are 32768 pages (64KiB page size, 2GiB max memory) and that would take up 4KiB just to track the free pages, plus if we're asked to mmap several pages together, we'd like to be able to search quickly for a block of free pages of the right size... What we'd need would be some kind of free-list data structure with sized bins and granular locking! Oh well... Nick ________________________________________ From: Rich Felker <dalias@aerifal.cx> on behalf of Rich Felker <dalias@libc.org> Sent: 28 November 2017 15:46:34 To: musl@lists.openwall.com Subject: Re: [musl] [PATCH] Wasm support patch 1 (support systems without mmap) On Tue, Nov 28, 2017 at 11:50:08AM +0000, Nicholas Wilson wrote: > I'm hoping the first patch is uncontroversial. > > WebAssembly has a linear/flat memory model, whereby it's simply > impossible for the addressable memory to contain "holes". Therefore, > mmap can't really be emulated, and all memory has to be allocated > via brk. This is not supported or supportable in musl's malloc. The heap that can be serviced by brk is only usable for allocation sizes less than ~128k. > I've done this by allowing malloc to fall back to brk (even for > allocations above MMAP_THRESHOLD) if mmap returns ENOSYS. > > It's one line of code that will do harm in "normal" systems, and > allows platforms that are emulating syscalls to choose not to > support mmap, and still get a working malloc if brk is working. The patch as written almost surely corrupts the heap structures or at least produces new heap expansion (no possibility of reuse) each time an allocation larger than ~128k is requested. This is because bin_index[_up] is not defined for n > MMAP_THRESHOLD. There are other places in musl that also depend on mmap working, like the TLS init code. brk on the other hand is only used as an optimization. I think what you should do, if it's hard to support both brk and mmap, is omit brk instead (have it return -ENOSYS), then have mmap always allocate lowest-available-page and keep some data structure (even just a bit array) representing which pages are free. This way you still keep everything in a contiguous range (possibly with some reusable gaps due to munmap) like you want. Rich > diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c > index 9e05e1d6..572232e1 100644 > --- a/src/malloc/malloc.c > +++ b/src/malloc/malloc.c > @@ -328,13 +328,17 @@ void *malloc(size_t n) > size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE; > char *base = __mmap(0, len, PROT_READ|PROT_WRITE, > MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); > - if (base == (void *)-1) return 0; > + if (base == MAP_FAILED) { > + if (errno == ENOSYS) goto nommap; > + return 0; > + } > c = (void *)(base + SIZE_ALIGN - OVERHEAD); > c->csize = len - (SIZE_ALIGN - OVERHEAD); > c->psize = SIZE_ALIGN - OVERHEAD; > return CHUNK_TO_MEM(c); > } > > +nommap: > i = bin_index_up(n); > for (;;) { > uint64_t mask = mal.binmap & -(1ULL<<i); > @@ -405,7 +409,7 @@ void *realloc(void *p, size_t n) > newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE; > if (oldlen == newlen) return p; > base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE); > - if (base == (void *)-1) > + if (base == MAP_FAILED) > goto copy_realloc; > self = (void *)(base + extra); > self->csize = newlen - extra; ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Wasm support patch 1 (support systems without mmap) 2017-11-28 16:34 ` Nicholas Wilson @ 2017-11-28 19:20 ` Rich Felker 0 siblings, 0 replies; 4+ messages in thread From: Rich Felker @ 2017-11-28 19:20 UTC (permalink / raw) To: musl On Tue, Nov 28, 2017 at 04:34:32PM +0000, Nicholas Wilson wrote: > Oh, I'd missed that. Let's scrap this patch then, I'll post an > updated version of Patch #3 (Wasm-specific files) that implements > mmap using Wasm's underlying "brk" capability. > > I could use a bitmap to track free pages - but there are 32768 pages > (64KiB page size, 2GiB max memory) and that would take up 4KiB just > to track the free pages, plus if we're asked to mmap several pages > together, we'd like to be able to search quickly for a block of free > pages of the right size... What we'd need would be some kind of > free-list data structure with sized bins and granular locking! Oh > well... Keep in mind that software does not expect syscalls to be fast, and malloc does not make mmap syscalls constantly, only when servicing big allocations (where usig the memory will dominate the allocation time) or expanding the heap (which happens a small bounded number of times). On real operating systems with kernel/user separation, syscalls involve overhead of at least 500-1000ns just to enter/exit the kernel. That's for trivial stuff like getpid. Since mmap involves locking vm structures, it's considerably more expensive than that. Searching a 4kB bit array likely has cost comparable to the syscall overhead, and thus is probably not a problem, but if it is, just use better data structures. Rich > ________________________________________ > From: Rich Felker <dalias@aerifal.cx> on behalf of Rich Felker <dalias@libc..org> > Sent: 28 November 2017 15:46:34 > To: musl@lists.openwall.com > Subject: Re: [musl] [PATCH] Wasm support patch 1 (support systems without mmap) > > On Tue, Nov 28, 2017 at 11:50:08AM +0000, Nicholas Wilson wrote: > > I'm hoping the first patch is uncontroversial. > > > > WebAssembly has a linear/flat memory model, whereby it's simply > > impossible for the addressable memory to contain "holes". Therefore, > > mmap can't really be emulated, and all memory has to be allocated > > via brk. > > This is not supported or supportable in musl's malloc. The heap that > can be serviced by brk is only usable for allocation sizes less than > ~128k. > > > I've done this by allowing malloc to fall back to brk (even for > > allocations above MMAP_THRESHOLD) if mmap returns ENOSYS. > > > > It's one line of code that will do harm in "normal" systems, and > > allows platforms that are emulating syscalls to choose not to > > support mmap, and still get a working malloc if brk is working. > > The patch as written almost surely corrupts the heap structures or at > least produces new heap expansion (no possibility of reuse) each time > an allocation larger than ~128k is requested. This is because > bin_index[_up] is not defined for n > MMAP_THRESHOLD. > > There are other places in musl that also depend on mmap working, like > the TLS init code. brk on the other hand is only used as an > optimization. I think what you should do, if it's hard to support both > brk and mmap, is omit brk instead (have it return -ENOSYS), then have > mmap always allocate lowest-available-page and keep some data > structure (even just a bit array) representing which pages are free. > This way you still keep everything in a contiguous range (possibly > with some reusable gaps due to munmap) like you want. > > Rich > > > > > diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c > > index 9e05e1d6..572232e1 100644 > > --- a/src/malloc/malloc.c > > +++ b/src/malloc/malloc.c > > @@ -328,13 +328,17 @@ void *malloc(size_t n) > > size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE; > > char *base = __mmap(0, len, PROT_READ|PROT_WRITE, > > MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); > > - if (base == (void *)-1) return 0; > > + if (base == MAP_FAILED) { > > + if (errno == ENOSYS) goto nommap; > > + return 0; > > + } > > c = (void *)(base + SIZE_ALIGN - OVERHEAD); > > c->csize = len - (SIZE_ALIGN - OVERHEAD); > > c->psize = SIZE_ALIGN - OVERHEAD; > > return CHUNK_TO_MEM(c); > > } > > > > +nommap: > > i = bin_index_up(n); > > for (;;) { > > uint64_t mask = mal.binmap & -(1ULL<<i); > > @@ -405,7 +409,7 @@ void *realloc(void *p, size_t n) > > newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE; > > if (oldlen == newlen) return p; > > base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE); > > - if (base == (void *)-1) > > + if (base == MAP_FAILED) > > goto copy_realloc; > > self = (void *)(base + extra); > > self->csize = newlen - extra; ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2017-11-28 19:20 UTC | newest] Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-11-28 11:50 [PATCH] Wasm support patch 1 (support systems without mmap) Nicholas Wilson 2017-11-28 15:46 ` Rich Felker 2017-11-28 16:34 ` Nicholas Wilson 2017-11-28 19:20 ` Rich Felker
Code repositories for project(s) associated with this public inbox https://git.vuxu.org/mirror/musl/ This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).