Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1829 insertions, 0 deletions

diff --git a/vendor/dlmalloc/src/dlmalloc.rs b/vendor/dlmalloc/src/dlmalloc.rs
new file mode 100644
index 000000000..a4b4b71b4
--- /dev/null
+++ b/vendor/dlmalloc/src/dlmalloc.rs
@@ -0,0 +1,1829 @@
+// This is a version of dlmalloc.c ported to Rust. You can find the original
+// source at ftp://g.oswego.edu/pub/misc/malloc.c
+//
+// The original source was written by Doug Lea and released to the public domain
+
+use core::cmp;
+use core::mem;
+use core::ptr;
+
+use Allocator;
+
+pub struct Dlmalloc<A> {
+    smallmap: u32,
+    treemap: u32,
+    smallbins: [*mut Chunk; (NSMALLBINS + 1) * 2],
+    treebins: [*mut TreeChunk; NTREEBINS],
+    dvsize: usize,
+    topsize: usize,
+    dv: *mut Chunk,
+    top: *mut Chunk,
+    footprint: usize,
+    max_footprint: usize,
+    seg: Segment,
+    trim_check: usize,
+    least_addr: *mut u8,
+    release_checks: usize,
+    system_allocator: A,
+}
+unsafe impl<A: Send> Send for Dlmalloc<A> {}
+
+// TODO: document this
+const NSMALLBINS: usize = 32;
+const NTREEBINS: usize = 32;
+const SMALLBIN_SHIFT: usize = 3;
+const TREEBIN_SHIFT: usize = 8;
+
+// TODO: runtime configurable? documentation?
+const DEFAULT_GRANULARITY: usize = 64 * 1024;
+const DEFAULT_TRIM_THRESHOLD: usize = 2 * 1024 * 1024;
+const MAX_RELEASE_CHECK_RATE: usize = 4095;
+
+#[repr(C)]
+struct Chunk {
+    prev_foot: usize,
+    head: usize,
+    prev: *mut Chunk,
+    next: *mut Chunk,
+}
+
+#[repr(C)]
+struct TreeChunk {
+    chunk: Chunk,
+    child: [*mut TreeChunk; 2],
+    parent: *mut TreeChunk,
+    index: u32,
+}
+
+#[repr(C)]
+#[derive(Clone, Copy)]
+struct Segment {
+    base: *mut u8,
+    size: usize,
+    next: *mut Segment,
+    flags: u32,
+}
+
+fn align_up(a: usize, alignment: usize) -> usize {
+    debug_assert!(alignment.is_power_of_two());
+    (a + (alignment - 1)) & !(alignment - 1)
+}
+
+fn left_bits(x: u32) -> u32 {
+    (x << 1) | (!(x << 1)).wrapping_add(1)
+}
+
+fn least_bit(x: u32) -> u32 {
+    x & (!x + 1)
+}
+
+fn leftshift_for_tree_index(x: u32) -> u32 {
+    let x = x as usize;
+    if x == NTREEBINS - 1 {
+        0
+    } else {
+        (mem::size_of::<usize>() * 8 - 1 - ((x >> 1) + TREEBIN_SHIFT - 2)) as u32
+    }
+}
+
+impl<A> Dlmalloc<A> {
+    pub const fn new(system_allocator: A) -> Dlmalloc<A> {
+        Dlmalloc {
+            smallmap: 0,
+            treemap: 0,
+            smallbins: [0 as *mut _; (NSMALLBINS + 1) * 2],
+            treebins: [0 as *mut _; NTREEBINS],
+            dvsize: 0,
+            topsize: 0,
+            dv: 0 as *mut _,
+            top: 0 as *mut _,
+            footprint: 0,
+            max_footprint: 0,
+            seg: Segment {
+                base: 0 as *mut _,
+                size: 0,
+                next: 0 as *mut _,
+                flags: 0,
+            },
+            trim_check: 0,
+            least_addr: 0 as *mut _,
+            release_checks: 0,
+            system_allocator,
+        }
+    }
+}
+
+impl<A: Allocator> Dlmalloc<A> {
+    // TODO: can we get rid of this?
+    pub fn malloc_alignment(&self) -> usize {
+        mem::size_of::<usize>() * 2
+    }
+
+    // TODO: dox
+    fn chunk_overhead(&self) -> usize {
+        mem::size_of::<usize>()
+    }
+
+    fn mmap_chunk_overhead(&self) -> usize {
+        2 * mem::size_of::<usize>()
+    }
+
+    // TODO: dox
+    fn min_large_size(&self) -> usize {
+        1 << TREEBIN_SHIFT
+    }
+
+    // TODO: dox
+    fn max_small_size(&self) -> usize {
+        self.min_large_size() - 1
+    }
+
+    // TODO: dox
+    fn max_small_request(&self) -> usize {
+        self.max_small_size() - (self.malloc_alignment() - 1) - self.chunk_overhead()
+    }
+
+    // TODO: dox
+    fn min_chunk_size(&self) -> usize {
+        align_up(mem::size_of::<Chunk>(), self.malloc_alignment())
+    }
+
+    // TODO: dox
+    fn min_request(&self) -> usize {
+        self.min_chunk_size() - self.chunk_overhead() - 1
+    }
+
+    // TODO: dox
+    fn max_request(&self) -> usize {
+        // min_sys_alloc_space: the largest `X` such that
+        //   pad_request(X - 1)        -- minus 1, because requests of exactly
+        //                                `max_request` will not be honored
+        //   + self.top_foot_size()
+        //   + self.malloc_alignment()
+        //   + DEFAULT_GRANULARITY
+        // ==
+        //   usize::MAX
+        let min_sys_alloc_space =
+            ((!0 - (DEFAULT_GRANULARITY + self.top_foot_size() + self.malloc_alignment()) + 1)
+                & !self.malloc_alignment())
+                - self.chunk_overhead()
+                + 1;
+
+        cmp::min((!self.min_chunk_size() + 1) << 2, min_sys_alloc_space)
+    }
+
+    fn pad_request(&self, amt: usize) -> usize {
+        align_up(amt + self.chunk_overhead(), self.malloc_alignment())
+    }
+
+    fn small_index(&self, size: usize) -> u32 {
+        (size >> SMALLBIN_SHIFT) as u32
+    }
+
+    fn small_index2size(&self, idx: u32) -> usize {
+        (idx as usize) << SMALLBIN_SHIFT
+    }
+
+    fn is_small(&self, s: usize) -> bool {
+        s >> SMALLBIN_SHIFT < NSMALLBINS
+    }
+
+    fn is_aligned(&self, a: usize) -> bool {
+        a & (self.malloc_alignment() - 1) == 0
+    }
+
+    fn align_offset(&self, addr: *mut u8) -> usize {
+        self.align_offset_usize(addr as usize)
+    }
+
+    fn align_offset_usize(&self, addr: usize) -> usize {
+        align_up(addr, self.malloc_alignment()) - (addr as usize)
+    }
+
+    fn top_foot_size(&self) -> usize {
+        self.align_offset_usize(Chunk::mem_offset() as usize)
+            + self.pad_request(mem::size_of::<Segment>())
+            + self.min_chunk_size()
+    }
+
+    fn mmap_foot_pad(&self) -> usize {
+        4 * mem::size_of::<usize>()
+    }
+
+    fn align_as_chunk(&self, ptr: *mut u8) -> *mut Chunk {
+        unsafe {
+            let chunk = Chunk::to_mem(ptr as *mut Chunk);
+            ptr.offset(self.align_offset(chunk) as isize) as *mut Chunk
+        }
+    }
+
+    fn request2size(&self, req: usize) -> usize {
+        if req < self.min_request() {
+            self.min_chunk_size()
+        } else {
+            self.pad_request(req)
+        }
+    }
+
+    unsafe fn overhead_for(&self, p: *mut Chunk) -> usize {
+        if Chunk::mmapped(p) {
+            self.mmap_chunk_overhead()
+        } else {
+            self.chunk_overhead()
+        }
+    }
+
+    pub unsafe fn calloc_must_clear(&self, ptr: *mut u8) -> bool {
+        !self.system_allocator.allocates_zeros() || !Chunk::mmapped(Chunk::from_mem(ptr))
+    }
+
+    pub unsafe fn malloc(&mut self, size: usize) -> *mut u8 {
+        self.check_malloc_state();
+
+        let nb;
+        if size <= self.max_small_request() {
+            nb = self.request2size(size);
+            let mut idx = self.small_index(nb);
+            let smallbits = self.smallmap >> idx;
+
+            // Check the bin for `idx` (the lowest bit) but also check the next
+            // bin up to use that to satisfy our request, if needed.
+            if smallbits & 0b11 != 0 {
+                // If our the lowest bit, our `idx`, is unset then bump up the
+                // index as we'll be using the next bucket up.
+                idx += !smallbits & 1;
+
+                let b = self.smallbin_at(idx);
+                let p = (*b).prev;
+                self.unlink_first_small_chunk(b, p, idx);
+                let smallsize = self.small_index2size(idx);
+                Chunk::set_inuse_and_pinuse(p, smallsize);
+                let ret = Chunk::to_mem(p);
+                self.check_malloced_chunk(ret, nb);
+                return ret;
+            }
+
+            if nb > self.dvsize {
+                // If there's some other bin with some memory, then we just use
+                // the next smallest bin
+                if smallbits != 0 {
+                    let leftbits = (smallbits << idx) & left_bits(1 << idx);
+                    let leastbit = least_bit(leftbits);
+                    let i = leastbit.trailing_zeros();
+                    let b = self.smallbin_at(i);
+                    let p = (*b).prev;
+                    debug_assert_eq!(Chunk::size(p), self.small_index2size(i));
+                    self.unlink_first_small_chunk(b, p, i);
+                    let smallsize = self.small_index2size(i);
+                    let rsize = smallsize - nb;
+                    if mem::size_of::<usize>() != 4 && rsize < self.min_chunk_size() {
+                        Chunk::set_inuse_and_pinuse(p, smallsize);
+                    } else {
+                        Chunk::set_size_and_pinuse_of_inuse_chunk(p, nb);
+                        let r = Chunk::plus_offset(p, nb);
+                        Chunk::set_size_and_pinuse_of_free_chunk(r, rsize);
+                        self.replace_dv(r, rsize);
+                    }
+                    let ret = Chunk::to_mem(p);
+                    self.check_malloced_chunk(ret, nb);
+                    return ret;
+                } else if self.treemap != 0 {
+                    let mem = self.tmalloc_small(nb);
+                    if !mem.is_null() {
+                        self.check_malloced_chunk(mem, nb);
+                        self.check_malloc_state();
+                        return mem;
+                    }
+                }
+            }
+        } else if size >= self.max_request() {
+            // TODO: translate this to unsupported
+            return ptr::null_mut();
+        } else {
+            nb = self.pad_request(size);
+            if self.treemap != 0 {
+                let mem = self.tmalloc_large(nb);
+                if !mem.is_null() {
+                    self.check_malloced_chunk(mem, nb);
+                    self.check_malloc_state();
+                    return mem;
+                }
+            }
+        }
+
+        // use the `dv` node if we can, splitting it if necessary or otherwise
+        // exhausting the entire chunk
+        if nb <= self.dvsize {
+            let rsize = self.dvsize - nb;
+            let p = self.dv;
+            if rsize >= self.min_chunk_size() {
+                self.dv = Chunk::plus_offset(p, nb);
+                self.dvsize = rsize;
+                let r = self.dv;
+                Chunk::set_size_and_pinuse_of_free_chunk(r, rsize);
+                Chunk::set_size_and_pinuse_of_inuse_chunk(p, nb);
+            } else {
+                let dvs = self.dvsize;
+                self.dvsize = 0;
+                self.dv = ptr::null_mut();
+                Chunk::set_inuse_and_pinuse(p, dvs);
+            }
+            let ret = Chunk::to_mem(p);
+            self.check_malloced_chunk(ret, nb);
+            self.check_malloc_state();
+            return ret;
+        }
+
+        // Split the top node if we can
+        if nb < self.topsize {
+            self.topsize -= nb;
+            let rsize = self.topsize;
+            let p = self.top;
+            self.top = Chunk::plus_offset(p, nb);
+            let r = self.top;
+            (*r).head = rsize | PINUSE;
+            Chunk::set_size_and_pinuse_of_inuse_chunk(p, nb);
+            self.check_top_chunk(self.top);
+            let ret = Chunk::to_mem(p);
+            self.check_malloced_chunk(ret, nb);
+            self.check_malloc_state();
+            return ret;
+        }
+
+        self.sys_alloc(nb)
+    }
+
+    /// allocates system resources
+    unsafe fn sys_alloc(&mut self, size: usize) -> *mut u8 {
+        self.check_malloc_state();
+        // keep in sync with max_request
+        let asize = align_up(
+            size + self.top_foot_size() + self.malloc_alignment(),
+            DEFAULT_GRANULARITY,
+        );
+
+        let (tbase, tsize, flags) = self.system_allocator.alloc(asize);
+        if tbase.is_null() {
+            return tbase;
+        }
+
+        self.footprint += tsize;
+        self.max_footprint = cmp::max(self.max_footprint, self.footprint);
+
+        if self.top.is_null() {
+            if self.least_addr.is_null() || tbase < self.least_addr {
+                self.least_addr = tbase;
+            }
+            self.seg.base = tbase;
+            self.seg.size = tsize;
+            self.seg.flags = flags;
+            self.release_checks = MAX_RELEASE_CHECK_RATE;
+            self.init_bins();
+            let tsize = tsize - self.top_foot_size();
+            self.init_top(tbase as *mut Chunk, tsize);
+        // let mn = Chunk::next(Chunk::from_mem(self as *mut _ as *mut u8));
+        // let top_foot_size = self.top_foot_size();
+        // self.init_top(mn, tbase as usize + tsize - mn as usize - top_foot_size);
+        } else {
+            let mut sp = &mut self.seg as *mut Segment;
+            while !sp.is_null() && tbase != Segment::top(sp) {
+                sp = (*sp).next;
+            }
+            if !sp.is_null()
+                && !Segment::is_extern(sp)
+                && Segment::sys_flags(sp) == flags
+                && Segment::holds(sp, self.top as *mut u8)
+            {
+                (*sp).size += tsize;
+                let ptr = self.top;
+                let size = self.topsize + tsize;
+                self.init_top(ptr, size);
+            } else {
+                self.least_addr = cmp::min(tbase, self.least_addr);
+                let mut sp = &mut self.seg as *mut Segment;
+                while !sp.is_null() && (*sp).base != tbase.offset(tsize as isize) {
+                    sp = (*sp).next;
+                }
+                if !sp.is_null() && !Segment::is_extern(sp) && Segment::sys_flags(sp) == flags {
+                    let oldbase = (*sp).base;
+                    (*sp).base = tbase;
+                    (*sp).size += tsize;
+                    return self.prepend_alloc(tbase, oldbase, size);
+                } else {
+                    self.add_segment(tbase, tsize, flags);
+                }
+            }
+        }
+
+        if size < self.topsize {
+            self.topsize -= size;
+            let rsize = self.topsize;
+            let p = self.top;
+            self.top = Chunk::plus_offset(p, size);
+            let r = self.top;
+            (*r).head = rsize | PINUSE;
+            Chunk::set_size_and_pinuse_of_inuse_chunk(p, size);
+            let ret = Chunk::to_mem(p);
+            self.check_top_chunk(self.top);
+            self.check_malloced_chunk(ret, size);
+            self.check_malloc_state();
+            return ret;
+        }
+
+        return ptr::null_mut();
+    }
+
+    pub unsafe fn realloc(&mut self, oldmem: *mut u8, bytes: usize) -> *mut u8 {
+        if bytes >= self.max_request() {
+            return ptr::null_mut();
+        }
+        let nb = self.request2size(bytes);
+        let oldp = Chunk::from_mem(oldmem);
+        let newp = self.try_realloc_chunk(oldp, nb, true);
+        if !newp.is_null() {
+            self.check_inuse_chunk(newp);
+            return Chunk::to_mem(newp);
+        }
+        let ptr = self.malloc(bytes);
+        if !ptr.is_null() {
+            let oc = Chunk::size(oldp) - self.overhead_for(oldp);
+            ptr::copy_nonoverlapping(oldmem, ptr, cmp::min(oc, bytes));
+            self.free(oldmem);
+        }
+        return ptr;
+    }
+
+    unsafe fn try_realloc_chunk(&mut self, p: *mut Chunk, nb: usize, can_move: bool) -> *mut Chunk {
+        let oldsize = Chunk::size(p);
+        let next = Chunk::plus_offset(p, oldsize);
+
+        if Chunk::mmapped(p) {
+            self.mmap_resize(p, nb, can_move)
+        } else if oldsize >= nb {
+            let rsize = oldsize - nb;
+            if rsize >= self.min_chunk_size() {
+                let r = Chunk::plus_offset(p, nb);
+                Chunk::set_inuse(p, nb);
+                Chunk::set_inuse(r, rsize);
+                self.dispose_chunk(r, rsize);
+            }
+            p
+        } else if next == self.top {
+            // extend into top
+            if oldsize + self.topsize <= nb {
+                return ptr::null_mut();
+            }
+            let newsize = oldsize + self.topsize;
+            let newtopsize = newsize - nb;
+            let newtop = Chunk::plus_offset(p, nb);
+            Chunk::set_inuse(p, nb);
+            (*newtop).head = newtopsize | PINUSE;
+            self.top = newtop;
+            self.topsize = newtopsize;
+            p
+        } else if next == self.dv {
+            // extend into dv
+            let dvs = self.dvsize;
+            if oldsize + dvs < nb {
+                return ptr::null_mut();
+            }
+            let dsize = oldsize + dvs - nb;
+            if dsize >= self.min_chunk_size() {
+                let r = Chunk::plus_offset(p, nb);
+                let n = Chunk::plus_offset(r, dsize);
+                Chunk::set_inuse(p, nb);
+                Chunk::set_size_and_pinuse_of_free_chunk(r, dsize);
+                Chunk::clear_pinuse(n);
+                self.dvsize = dsize;
+                self.dv = r;
+            } else {
+                // exhaust dv
+                let newsize = oldsize + dvs;
+                Chunk::set_inuse(p, newsize);
+                self.dvsize = 0;
+                self.dv = ptr::null_mut();
+            }
+            return p;
+        } else if !Chunk::cinuse(next) {
+            // extend into the next free chunk
+            let nextsize = Chunk::size(next);
+            if oldsize + nextsize < nb {
+                return ptr::null_mut();
+            }
+            let rsize = oldsize + nextsize - nb;
+            self.unlink_chunk(next, nextsize);
+            if rsize < self.min_chunk_size() {
+                let newsize = oldsize + nextsize;
+                Chunk::set_inuse(p, newsize);
+            } else {
+                let r = Chunk::plus_offset(p, nb);
+                Chunk::set_inuse(p, nb);
+                Chunk::set_inuse(r, rsize);
+                self.dispose_chunk(r, rsize);
+            }
+            p
+        } else {
+            ptr::null_mut()
+        }
+    }
+
+    unsafe fn mmap_resize(&mut self, oldp: *mut Chunk, nb: usize, can_move: bool) -> *mut Chunk {
+        let oldsize = Chunk::size(oldp);
+        // Can't shrink mmap regions below a small size
+        if self.is_small(nb) {
+            return ptr::null_mut();
+        }
+
+        // Keep the old chunk if it's big enough but not too big
+        if oldsize >= nb + mem::size_of::<usize>() && (oldsize - nb) <= (DEFAULT_GRANULARITY << 1) {
+            return oldp;
+        }
+
+        let offset = (*oldp).prev_foot;
+        let oldmmsize = oldsize + offset + self.mmap_foot_pad();
+        let newmmsize =
+            self.mmap_align(nb + 6 * mem::size_of::<usize>() + self.malloc_alignment() - 1);
+        let ptr = self.system_allocator.remap(
+            (oldp as *mut u8).offset(-(offset as isize)),
+            oldmmsize,
+            newmmsize,
+            can_move,
+        );
+        if ptr.is_null() {
+            return ptr::null_mut();
+        }
+        let newp = ptr.offset(offset as isize) as *mut Chunk;
+        let psize = newmmsize - offset - self.mmap_foot_pad();
+        (*newp).head = psize;
+        (*Chunk::plus_offset(newp, psize)).head = Chunk::fencepost_head();
+        (*Chunk::plus_offset(newp, psize + mem::size_of::<usize>())).head = 0;
+        self.least_addr = cmp::min(ptr, self.least_addr);
+        self.footprint = self.footprint + newmmsize - oldmmsize;
+        self.max_footprint = cmp::max(self.max_footprint, self.footprint);
+        self.check_mmapped_chunk(newp);
+        return newp;
+    }
+
+    fn mmap_align(&self, a: usize) -> usize {
+        align_up(a, self.system_allocator.page_size())
+    }
+
+    // Only call this with power-of-two alignment and alignment >
+    // `self.malloc_alignment()`
+    pub unsafe fn memalign(&mut self, mut alignment: usize, bytes: usize) -> *mut u8 {
+        if alignment < self.min_chunk_size() {
+            alignment = self.min_chunk_size();
+        }
+        if bytes >= self.max_request() - alignment {
+            return ptr::null_mut();
+        }
+        let nb = self.request2size(bytes);
+        let req = nb + alignment + self.min_chunk_size() - self.chunk_overhead();
+        let mem = self.malloc(req);
+        if mem.is_null() {
+            return mem;
+        }
+        let mut p = Chunk::from_mem(mem);
+        if mem as usize & (alignment - 1) != 0 {
+            // Here we find an aligned sopt inside the chunk. Since we need to
+            // give back leading space in a chunk of at least `min_chunk_size`,
+            // if the first calculation places us at a spot with less than
+            // `min_chunk_size` leader we can move to the next aligned spot.
+            // we've allocated enough total room so that this is always possible
+            let br =
+                Chunk::from_mem(((mem as usize + alignment - 1) & (!alignment + 1)) as *mut u8);
+            let pos = if (br as usize - p as usize) > self.min_chunk_size() {
+                br as *mut u8
+            } else {
+                (br as *mut u8).offset(alignment as isize)
+            };
+            let newp = pos as *mut Chunk;
+            let leadsize = pos as usize - p as usize;
+            let newsize = Chunk::size(p) - leadsize;
+
+            // for mmapped chunks just adjust the offset
+            if Chunk::mmapped(p) {
+                (*newp).prev_foot = (*p).prev_foot + leadsize;
+                (*newp).head = newsize;
+            } else {
+                // give back the leader, use the rest
+                Chunk::set_inuse(newp, newsize);
+                Chunk::set_inuse(p, leadsize);
+                self.dispose_chunk(p, leadsize);
+            }
+            p = newp;
+        }
+
+        // give back spare room at the end
+        if !Chunk::mmapped(p) {
+            let size = Chunk::size(p);
+            if size > nb + self.min_chunk_size() {
+                let remainder_size = size - nb;
+                let remainder = Chunk::plus_offset(p, nb);
+                Chunk::set_inuse(p, nb);
+                Chunk::set_inuse(remainder, remainder_size);
+                self.dispose_chunk(remainder, remainder_size);
+            }
+        }
+
+        let mem = Chunk::to_mem(p);
+        debug_assert!(Chunk::size(p) >= nb);
+        debug_assert_eq!(align_up(mem as usize, alignment), mem as usize);
+        self.check_inuse_chunk(p);
+        return mem;
+    }
+
+    // consolidate and bin a chunk, differs from exported versions of free
+    // mainly in that the chunk need not be marked as inuse
+    unsafe fn dispose_chunk(&mut self, mut p: *mut Chunk, mut psize: usize) {
+        let next = Chunk::plus_offset(p, psize);
+        if !Chunk::pinuse(p) {
+            let prevsize = (*p).prev_foot;
+            if Chunk::mmapped(p) {
+                psize += prevsize + self.mmap_foot_pad();
+                if self
+                    .system_allocator
+                    .free((p as *mut u8).offset(-(prevsize as isize)), psize)
+                {
+                    self.footprint -= psize;
+                }
+                return;
+            }
+            let prev = Chunk::minus_offset(p, prevsize);
+            psize += prevsize;
+            p = prev;
+            if p != self.dv {
+                self.unlink_chunk(p, prevsize);
+            } else if (*next).head & INUSE == INUSE {
+                self.dvsize = psize;
+                Chunk::set_free_with_pinuse(p, psize, next);
+                return;
+            }
+        }
+
+        if !Chunk::cinuse(next) {
+            // consolidate forward
+            if next == self.top {
+                self.topsize += psize;
+                let tsize = self.topsize;
+                self.top = p;
+                (*p).head = tsize | PINUSE;
+                if p == self.dv {
+                    self.dv = ptr::null_mut();
+                    self.dvsize = 0;
+                }
+                return;
+            } else if next == self.dv {
+                self.dvsize += psize;
+                let dsize = self.dvsize;
+                self.dv = p;
+                Chunk::set_size_and_pinuse_of_free_chunk(p, dsize);
+                return;
+            } else {
+                let nsize = Chunk::size(next);
+                psize += nsize;
+                self.unlink_chunk(next, nsize);
+                Chunk::set_size_and_pinuse_of_free_chunk(p, psize);
+                if p == self.dv {
+                    self.dvsize = psize;
+                    return;
+                }
+            }
+        } else {
+            Chunk::set_free_with_pinuse(p, psize, next);
+        }
+        self.insert_chunk(p, psize);
+    }
+
+    unsafe fn init_top(&mut self, ptr: *mut Chunk, size: usize) {
+        let offset = self.align_offset(Chunk::to_mem(ptr));
+        let p = Chunk::plus_offset(ptr, offset);
+        let size = size - offset;
+
+        self.top = p;
+        self.topsize = size;
+        (*p).head = size | PINUSE;
+        (*Chunk::plus_offset(p, size)).head = self.top_foot_size();
+        self.trim_check = DEFAULT_TRIM_THRESHOLD;
+    }
+
+    unsafe fn init_bins(&mut self) {
+        for i in 0..NSMALLBINS as u32 {
+            let bin = self.smallbin_at(i);
+            (*bin).next = bin;
+            (*bin).prev = bin;
+        }
+    }
+
+    unsafe fn prepend_alloc(&mut self, newbase: *mut u8, oldbase: *mut u8, size: usize) -> *mut u8 {
+        let p = self.align_as_chunk(newbase);
+        let mut oldfirst = self.align_as_chunk(oldbase);
+        let psize = oldfirst as usize - p as usize;
+        let q = Chunk::plus_offset(p, size);
+        let mut qsize = psize - size;
+        Chunk::set_size_and_pinuse_of_inuse_chunk(p, size);
+
+        debug_assert!(oldfirst > q);
+        debug_assert!(Chunk::pinuse(oldfirst));
+        debug_assert!(qsize >= self.min_chunk_size());
+
+        // consolidate the remainder with the first chunk of the old base
+        if oldfirst == self.top {
+            self.topsize += qsize;
+            let tsize = self.topsize;
+            self.top = q;
+            (*q).head = tsize | PINUSE;
+            self.check_top_chunk(q);
+        } else if oldfirst == self.dv {
+            self.dvsize += qsize;
+            let dsize = self.dvsize;
+            self.dv = q;
+            Chunk::set_size_and_pinuse_of_free_chunk(q, dsize);
+        } else {
+            if !Chunk::inuse(oldfirst) {
+                let nsize = Chunk::size(oldfirst);
+                self.unlink_chunk(oldfirst, nsize);
+                oldfirst = Chunk::plus_offset(oldfirst, nsize);
+                qsize += nsize;
+            }
+            Chunk::set_free_with_pinuse(q, qsize, oldfirst);
+            self.insert_chunk(q, qsize);
+            self.check_free_chunk(q);
+        }
+
+        let ret = Chunk::to_mem(p);
+        self.check_malloced_chunk(ret, size);
+        self.check_malloc_state();
+        return ret;
+    }
+
+    // add a segment to hold a new noncontiguous region
+    unsafe fn add_segment(&mut self, tbase: *mut u8, tsize: usize, flags: u32) {
+        // TODO: what in the world is this function doing
+
+        // Determine locations and sizes of segment, fenceposts, and the old top
+        let old_top = self.top as *mut u8;
+        let oldsp = self.segment_holding(old_top);
+        let old_end = Segment::top(oldsp);
+        let ssize = self.pad_request(mem::size_of::<Segment>());
+        let offset = ssize + mem::size_of::<usize>() * 4 + self.malloc_alignment() - 1;
+        let rawsp = old_end.offset(-(offset as isize));
+        let offset = self.align_offset(Chunk::to_mem(rawsp as *mut Chunk));
+        let asp = rawsp.offset(offset as isize);
+        let csp = if asp < old_top.offset(self.min_chunk_size() as isize) {
+            old_top
+        } else {
+            asp
+        };
+        let sp = csp as *mut Chunk;
+        let ss = Chunk::to_mem(sp) as *mut Segment;
+        let tnext = Chunk::plus_offset(sp, ssize);
+        let mut p = tnext;
+        let mut nfences = 0;
+
+        // reset the top to our new space
+        let size = tsize - self.top_foot_size();
+        self.init_top(tbase as *mut Chunk, size);
+
+        // set up our segment record
+        debug_assert!(self.is_aligned(ss as usize));
+        Chunk::set_size_and_pinuse_of_inuse_chunk(sp, ssize);
+        *ss = self.seg; // push our current record
+        self.seg.base = tbase;
+        self.seg.size = tsize;
+        self.seg.flags = flags;
+        self.seg.next = ss;
+
+        // insert trailing fences
+        loop {
+            let nextp = Chunk::plus_offset(p, mem::size_of::<usize>());
+            (*p).head = Chunk::fencepost_head();
+            nfences += 1;
+            if (&(*nextp).head as *const usize as *mut u8) < old_end {
+                p = nextp;
+            } else {
+                break;
+            }
+        }
+        debug_assert!(nfences >= 2);
+
+        // insert the rest of the old top into a bin as an ordinary free chunk
+        if csp != old_top {
+            let q = old_top as *mut Chunk;
+            let psize = csp as usize - old_top as usize;
+            let tn = Chunk::plus_offset(q, psize);
+            Chunk::set_free_with_pinuse(q, psize, tn);
+            self.insert_chunk(q, psize);
+        }
+
+        self.check_top_chunk(self.top);
+        self.check_malloc_state();
+    }
+
+    unsafe fn segment_holding(&self, ptr: *mut u8) -> *mut Segment {
+        let mut sp = &self.seg as *const Segment as *mut Segment;
+        while !sp.is_null() {
+            if (*sp).base <= ptr && ptr < Segment::top(sp) {
+                return sp;
+            }
+            sp = (*sp).next;
+        }
+        ptr::null_mut()
+    }
+
+    unsafe fn tmalloc_small(&mut self, size: usize) -> *mut u8 {
+        let leastbit = least_bit(self.treemap);
+        let i = leastbit.trailing_zeros();
+        let mut v = *self.treebin_at(i);
+        let mut t = v;
+        let mut rsize = Chunk::size(TreeChunk::chunk(t)) - size;
+
+        loop {
+            t = TreeChunk::leftmost_child(t);
+            if t.is_null() {
+                break;
+            }
+            let trem = Chunk::size(TreeChunk::chunk(t)) - size;
+            if trem < rsize {
+                rsize = trem;
+                v = t;
+            }
+        }
+
+        let vc = TreeChunk::chunk(v);
+        let r = Chunk::plus_offset(vc, size) as *mut TreeChunk;
+        debug_assert_eq!(Chunk::size(vc), rsize + size);
+        self.unlink_large_chunk(v);
+        if rsize < self.min_chunk_size() {
+            Chunk::set_inuse_and_pinuse(vc, rsize + size);
+        } else {
+            let rc = TreeChunk::chunk(r);
+            Chunk::set_size_and_pinuse_of_inuse_chunk(vc, size);
+            Chunk::set_size_and_pinuse_of_free_chunk(rc, rsize);
+            self.replace_dv(rc, rsize);
+        }
+        Chunk::to_mem(vc)
+    }
+
+    unsafe fn tmalloc_large(&mut self, size: usize) -> *mut u8 {
+        let mut v = ptr::null_mut();
+        let mut rsize = !size + 1;
+        let idx = self.compute_tree_index(size);
+        let mut t = *self.treebin_at(idx);
+        if !t.is_null() {
+            // Traverse thre tree for this bin looking for a node with size
+            // equal to the `size` above.
+            let mut sizebits = size << leftshift_for_tree_index(idx);
+            // Keep track of the deepest untaken right subtree
+            let mut rst = ptr::null_mut();
+            loop {
+                let csize = Chunk::size(TreeChunk::chunk(t));
+                if csize >= size && csize - size < rsize {
+                    v = t;
+                    rsize = csize - size;
+                    if rsize == 0 {
+                        break;
+                    }
+                }
+                let rt = (*t).child[1];
+                t = (*t).child[(sizebits >> (mem::size_of::<usize>() * 8 - 1)) & 1];
+                if !rt.is_null() && rt != t {
+                    rst = rt;
+                }
+                if t.is_null() {
+                    // Reset `t` to the least subtree holding sizes greater than
+                    // the `size` above, breaking out
+                    t = rst;
+                    break;
+                }
+                sizebits <<= 1;
+            }
+        }
+
+        // Set t to the root of the next non-empty treebin
+        if t.is_null() && v.is_null() {
+            let leftbits = left_bits(1 << idx) & self.treemap;
+            if leftbits != 0 {
+                let leastbit = least_bit(leftbits);
+                let i = leastbit.trailing_zeros();
+                t = *self.treebin_at(i);
+            }
+        }
+
+        // Find the smallest of this tree or subtree
+        while !t.is_null() {
+            let csize = Chunk::size(TreeChunk::chunk(t));
+            if csize >= size && csize - size < rsize {
+                rsize = csize - size;
+                v = t;
+            }
+            t = TreeChunk::leftmost_child(t);
+        }
+
+        // If dv is a better fit, then return null so malloc will use it
+        if v.is_null() || (self.dvsize >= size && !(rsize < self.dvsize - size)) {
+            return ptr::null_mut();
+        }
+
+        let vc = TreeChunk::chunk(v);
+        let r = Chunk::plus_offset(vc, size);
+        debug_assert_eq!(Chunk::size(vc), rsize + size);
+        self.unlink_large_chunk(v);
+        if rsize < self.min_chunk_size() {
+            Chunk::set_inuse_and_pinuse(vc, rsize + size);
+        } else {
+            Chunk::set_size_and_pinuse_of_inuse_chunk(vc, size);
+            Chunk::set_size_and_pinuse_of_free_chunk(r, rsize);
+            self.insert_chunk(r, rsize);
+        }
+        Chunk::to_mem(vc)
+    }
+
+    unsafe fn smallbin_at(&mut self, idx: u32) -> *mut Chunk {
+        debug_assert!(((idx * 2) as usize) < self.smallbins.len());
+        &mut *self.smallbins.get_unchecked_mut((idx as usize) * 2) as *mut *mut Chunk as *mut Chunk
+    }
+
+    unsafe fn treebin_at(&mut self, idx: u32) -> *mut *mut TreeChunk {
+        debug_assert!((idx as usize) < self.treebins.len());
+        &mut *self.treebins.get_unchecked_mut(idx as usize)
+    }
+
+    fn compute_tree_index(&self, size: usize) -> u32 {
+        let x = size >> TREEBIN_SHIFT;
+        if x == 0 {
+            0
+        } else if x > 0xffff {
+            NTREEBINS as u32 - 1
+        } else {
+            let k = mem::size_of_val(&x) * 8 - 1 - (x.leading_zeros() as usize);
+            ((k << 1) + (size >> (k + TREEBIN_SHIFT - 1) & 1)) as u32
+        }
+    }
+
+    unsafe fn unlink_first_small_chunk(&mut self, head: *mut Chunk, next: *mut Chunk, idx: u32) {
+        let ptr = (*next).prev;
+        debug_assert!(next != head);
+        debug_assert!(next != ptr);
+        debug_assert_eq!(Chunk::size(next), self.small_index2size(idx));
+        if head == ptr {
+            self.clear_smallmap(idx);
+        } else {
+            (*ptr).next = head;
+            (*head).prev = ptr;
+        }
+    }
+
+    unsafe fn replace_dv(&mut self, chunk: *mut Chunk, size: usize) {
+        let dvs = self.dvsize;
+        debug_assert!(self.is_small(dvs));
+        if dvs != 0 {
+            let dv = self.dv;
+            self.insert_small_chunk(dv, dvs);
+        }
+        self.dvsize = size;
+        self.dv = chunk;
+    }
+
+    unsafe fn insert_chunk(&mut self, chunk: *mut Chunk, size: usize) {
+        if self.is_small(size) {
+            self.insert_small_chunk(chunk, size);
+        } else {
+            self.insert_large_chunk(chunk as *mut TreeChunk, size);
+        }
+    }
+
+    unsafe fn insert_small_chunk(&mut self, chunk: *mut Chunk, size: usize) {
+        let idx = self.small_index(size);
+        let head = self.smallbin_at(idx);
+        let mut f = head;
+        debug_assert!(size >= self.min_chunk_size());
+        if !self.smallmap_is_marked(idx) {
+            self.mark_smallmap(idx);
+        } else {
+            f = (*head).prev;
+        }
+
+        (*head).prev = chunk;
+        (*f).next = chunk;
+        (*chunk).prev = f;
+        (*chunk).next = head;
+    }
+
+    unsafe fn insert_large_chunk(&mut self, chunk: *mut TreeChunk, size: usize) {
+        let idx = self.compute_tree_index(size);
+        let h = self.treebin_at(idx);
+        (*chunk).index = idx;
+        (*chunk).child[0] = ptr::null_mut();
+        (*chunk).child[1] = ptr::null_mut();
+        let chunkc = TreeChunk::chunk(chunk);
+        if !self.treemap_is_marked(idx) {
+            self.mark_treemap(idx);
+            *h = chunk;
+            (*chunk).parent = h as *mut TreeChunk; // TODO: dubious?
+            (*chunkc).next = chunkc;
+            (*chunkc).prev = chunkc;
+        } else {
+            let mut t = *h;
+            let mut k = size << leftshift_for_tree_index(idx);
+            loop {
+                if Chunk::size(TreeChunk::chunk(t)) != size {
+                    let c = &mut (*t).child[(k >> mem::size_of::<usize>() * 8 - 1) & 1];
+                    k <<= 1;
+                    if !c.is_null() {
+                        t = *c;
+                    } else {
+                        *c = chunk;
+                        (*chunk).parent = t;
+                        (*chunkc).next = chunkc;
+                        (*chunkc).prev = chunkc;
+                        break;
+                    }
+                } else {
+                    let tc = TreeChunk::chunk(t);
+                    let f = (*tc).prev;
+                    (*f).next = chunkc;
+                    (*tc).prev = chunkc;
+                    (*chunkc).prev = f;
+                    (*chunkc).next = tc;
+                    (*chunk).parent = ptr::null_mut();
+                    break;
+                }
+            }
+        }
+    }
+
+    unsafe fn smallmap_is_marked(&self, idx: u32) -> bool {
+        self.smallmap & (1 << idx) != 0
+    }
+
+    unsafe fn mark_smallmap(&mut self, idx: u32) {
+        self.smallmap |= 1 << idx;
+    }
+
+    unsafe fn clear_smallmap(&mut self, idx: u32) {
+        self.smallmap &= !(1 << idx);
+    }
+
+    unsafe fn treemap_is_marked(&self, idx: u32) -> bool {
+        self.treemap & (1 << idx) != 0
+    }
+
+    unsafe fn mark_treemap(&mut self, idx: u32) {
+        self.treemap |= 1 << idx;
+    }
+
+    unsafe fn clear_treemap(&mut self, idx: u32) {
+        self.treemap &= !(1 << idx);
+    }
+
+    unsafe fn unlink_chunk(&mut self, chunk: *mut Chunk, size: usize) {
+        if self.is_small(size) {
+            self.unlink_small_chunk(chunk, size)
+        } else {
+            self.unlink_large_chunk(chunk as *mut TreeChunk);
+        }
+    }
+
+    unsafe fn unlink_small_chunk(&mut self, chunk: *mut Chunk, size: usize) {
+        let f = (*chunk).prev;
+        let b = (*chunk).next;
+        let idx = self.small_index(size);
+        debug_assert!(chunk != b);
+        debug_assert!(chunk != f);
+        debug_assert_eq!(Chunk::size(chunk), self.small_index2size(idx));
+        if b == f {
+            self.clear_smallmap(idx);
+        } else {
+            (*f).next = b;
+            (*b).prev = f;
+        }
+    }
+
+    unsafe fn unlink_large_chunk(&mut self, chunk: *mut TreeChunk) {
+        let xp = (*chunk).parent;
+        let mut r;
+        if TreeChunk::next(chunk) != chunk {
+            let f = TreeChunk::prev(chunk);
+            r = TreeChunk::next(chunk);
+            (*f).chunk.next = TreeChunk::chunk(r);
+            (*r).chunk.prev = TreeChunk::chunk(f);
+        } else {
+            let mut rp = &mut (*chunk).child[1];
+            if rp.is_null() {
+                rp = &mut (*chunk).child[0];
+            }
+            r = *rp;
+            if !rp.is_null() {
+                loop {
+                    let mut cp = &mut (**rp).child[1];
+                    if cp.is_null() {
+                        cp = &mut (**rp).child[0];
+                    }
+                    if cp.is_null() {
+                        break;
+                    }
+                    rp = cp;
+                }
+                r = *rp;
+                *rp = ptr::null_mut();
+            }
+        }
+
+        if xp.is_null() {
+            return;
+        }
+
+        let h = self.treebin_at((*chunk).index);
+        if chunk == *h {
+            *h = r;
+            if r.is_null() {
+                self.clear_treemap((*chunk).index);
+            }
+        } else {
+            if (*xp).child[0] == chunk {
+                (*xp).child[0] = r;
+            } else {
+                (*xp).child[1] = r;
+            }
+        }
+
+        if !r.is_null() {
+            (*r).parent = xp;
+            let c0 = (*chunk).child[0];
+            if !c0.is_null() {
+                (*r).child[0] = c0;
+                (*c0).parent = r;
+            }
+            let c1 = (*chunk).child[1];
+            if !c1.is_null() {
+                (*r).child[1] = c1;
+                (*c1).parent = r;
+            }
+        }
+    }
+
+    pub unsafe fn free(&mut self, mem: *mut u8) {
+        self.check_malloc_state();
+
+        let mut p = Chunk::from_mem(mem);
+        let mut psize = Chunk::size(p);
+        let next = Chunk::plus_offset(p, psize);
+        if !Chunk::pinuse(p) {
+            let prevsize = (*p).prev_foot;
+
+            if Chunk::mmapped(p) {
+                psize += prevsize + self.mmap_foot_pad();
+                if self
+                    .system_allocator
+                    .free((p as *mut u8).offset(-(prevsize as isize)), psize)
+                {
+                    self.footprint -= psize;
+                }
+                return;
+            }
+
+            let prev = Chunk::minus_offset(p, prevsize);
+            psize += prevsize;
+            p = prev;
+            if p != self.dv {
+                self.unlink_chunk(p, prevsize);
+            } else if (*next).head & INUSE == INUSE {
+                self.dvsize = psize;
+                Chunk::set_free_with_pinuse(p, psize, next);
+                return;
+            }
+        }
+
+        // Consolidate forward if we can
+        if !Chunk::cinuse(next) {
+            if next == self.top {
+                self.topsize += psize;
+                let tsize = self.topsize;
+                self.top = p;
+                (*p).head = tsize | PINUSE;
+                if p == self.dv {
+                    self.dv = ptr::null_mut();
+                    self.dvsize = 0;
+                }
+                if self.should_trim(tsize) {
+                    self.sys_trim(0);
+                }
+                return;
+            } else if next == self.dv {
+                self.dvsize += psize;
+                let dsize = self.dvsize;
+                self.dv = p;
+                Chunk::set_size_and_pinuse_of_free_chunk(p, dsize);
+                return;
+            } else {
+                let nsize = Chunk::size(next);
+                psize += nsize;
+                self.unlink_chunk(next, nsize);
+                Chunk::set_size_and_pinuse_of_free_chunk(p, psize);
+                if p == self.dv {
+                    self.dvsize = psize;
+                    return;
+                }
+            }
+        } else {
+            Chunk::set_free_with_pinuse(p, psize, next);
+        }
+
+        if self.is_small(psize) {
+            self.insert_small_chunk(p, psize);
+            self.check_free_chunk(p);
+        } else {
+            self.insert_large_chunk(p as *mut TreeChunk, psize);
+            self.check_free_chunk(p);
+            self.release_checks -= 1;
+            if self.release_checks == 0 {
+                self.release_unused_segments();
+            }
+        }
+    }
+
+    fn should_trim(&self, size: usize) -> bool {
+        size > self.trim_check
+    }
+
+    unsafe fn sys_trim(&mut self, mut pad: usize) -> bool {
+        let mut released = 0;
+        if pad < self.max_request() && !self.top.is_null() {
+            pad += self.top_foot_size();
+            if self.topsize > pad {
+                let unit = DEFAULT_GRANULARITY;
+                let extra = ((self.topsize - pad + unit - 1) / unit - 1) * unit;
+                let sp = self.segment_holding(self.top as *mut u8);
+                debug_assert!(!sp.is_null());
+
+                if !Segment::is_extern(sp) {
+                    if Segment::can_release_part(&self.system_allocator, sp) {
+                        if (*sp).size >= extra && !self.has_segment_link(sp) {
+                            let newsize = (*sp).size - extra;
+                            if self
+                                .system_allocator
+                                .free_part((*sp).base, (*sp).size, newsize)
+                            {
+                                released = extra;
+                            }
+                        }
+                    }
+                }
+
+                if released != 0 {
+                    (*sp).size -= released;
+                    self.footprint -= released;
+                    let top = self.top;
+                    let topsize = self.topsize - released;
+                    self.init_top(top, topsize);
+                    self.check_top_chunk(self.top);
+                }
+            }
+
+            released += self.release_unused_segments();
+
+            if released == 0 && self.topsize > self.trim_check {
+                self.trim_check = usize::max_value();
+            }
+        }
+
+        released != 0
+    }
+
+    unsafe fn has_segment_link(&self, ptr: *mut Segment) -> bool {
+        let mut sp = &self.seg as *const Segment as *mut Segment;
+        while !sp.is_null() {
+            if Segment::holds(ptr, sp as *mut u8) {
+                return true;
+            }
+            sp = (*sp).next;
+        }
+        false
+    }
+
+    /// Unmap and unlink any mapped segments that don't contain used chunks
+    unsafe fn release_unused_segments(&mut self) -> usize {
+        let mut released = 0;
+        let mut nsegs = 0;
+        let mut pred = &mut self.seg as *mut Segment;
+        let mut sp = (*pred).next;
+        while !sp.is_null() {
+            let base = (*sp).base;
+            let size = (*sp).size;
+            let next = (*sp).next;
+            nsegs += 1;
+
+            if Segment::can_release_part(&self.system_allocator, sp) && !Segment::is_extern(sp) {
+                let p = self.align_as_chunk(base);
+                let psize = Chunk::size(p);
+                // We can unmap if the first chunk holds the entire segment and
+                // isn't pinned.
+                let chunk_top = (p as *mut u8).offset(psize as isize);
+                let top = base.offset((size - self.top_foot_size()) as isize);
+                if !Chunk::inuse(p) && chunk_top >= top {
+                    let tp = p as *mut TreeChunk;
+                    debug_assert!(Segment::holds(sp, sp as *mut u8));
+                    if p == self.dv {
+                        self.dv = ptr::null_mut();
+                        self.dvsize = 0;
+                    } else {
+                        self.unlink_large_chunk(tp);
+                    }
+                    if self.system_allocator.free(base, size) {
+                        released += size;
+                        self.footprint -= size;
+                        // unlink our obsolete record
+                        sp = pred;
+                        (*sp).next = next;
+                    } else {
+                        // back out if we can't unmap
+                        self.insert_large_chunk(tp, psize);
+                    }
+                }
+            }
+            pred = sp;
+            sp = next;
+        }
+        self.release_checks = if nsegs > MAX_RELEASE_CHECK_RATE {
+            nsegs
+        } else {
+            MAX_RELEASE_CHECK_RATE
+        };
+        return released;
+    }
+
+    // Sanity checks
+
+    unsafe fn check_any_chunk(&self, p: *mut Chunk) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        debug_assert!(
+            self.is_aligned(Chunk::to_mem(p) as usize) || (*p).head == Chunk::fencepost_head()
+        );
+        debug_assert!(p as *mut u8 >= self.least_addr);
+    }
+
+    unsafe fn check_top_chunk(&self, p: *mut Chunk) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        let sp = self.segment_holding(p as *mut u8);
+        let sz = (*p).head & !INUSE;
+        debug_assert!(!sp.is_null());
+        debug_assert!(
+            self.is_aligned(Chunk::to_mem(p) as usize) || (*p).head == Chunk::fencepost_head()
+        );
+        debug_assert!(p as *mut u8 >= self.least_addr);
+        debug_assert_eq!(sz, self.topsize);
+        debug_assert!(sz > 0);
+        debug_assert_eq!(
+            sz,
+            (*sp).base as usize + (*sp).size - p as usize - self.top_foot_size()
+        );
+        debug_assert!(Chunk::pinuse(p));
+        debug_assert!(!Chunk::pinuse(Chunk::plus_offset(p, sz)));
+    }
+
+    unsafe fn check_malloced_chunk(&self, mem: *mut u8, s: usize) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        if mem.is_null() {
+            return;
+        }
+        let p = Chunk::from_mem(mem);
+        let sz = (*p).head & !INUSE;
+        self.check_inuse_chunk(p);
+        debug_assert_eq!(align_up(sz, self.malloc_alignment()), sz);
+        debug_assert!(sz >= self.min_chunk_size());
+        debug_assert!(sz >= s);
+        debug_assert!(Chunk::mmapped(p) || sz < (s + self.min_chunk_size()));
+    }
+
+    unsafe fn check_inuse_chunk(&self, p: *mut Chunk) {
+        self.check_any_chunk(p);
+        debug_assert!(Chunk::inuse(p));
+        debug_assert!(Chunk::pinuse(Chunk::next(p)));
+        debug_assert!(Chunk::mmapped(p) || Chunk::pinuse(p) || Chunk::next(Chunk::prev(p)) == p);
+        if Chunk::mmapped(p) {
+            self.check_mmapped_chunk(p);
+        }
+    }
+
+    unsafe fn check_mmapped_chunk(&self, p: *mut Chunk) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        let sz = Chunk::size(p);
+        let len = sz + (*p).prev_foot + self.mmap_foot_pad();
+        debug_assert!(Chunk::mmapped(p));
+        debug_assert!(
+            self.is_aligned(Chunk::to_mem(p) as usize) || (*p).head == Chunk::fencepost_head()
+        );
+        debug_assert!(p as *mut u8 >= self.least_addr);
+        debug_assert!(!self.is_small(sz));
+        debug_assert_eq!(align_up(len, self.system_allocator.page_size()), len);
+        debug_assert_eq!((*Chunk::plus_offset(p, sz)).head, Chunk::fencepost_head());
+        debug_assert_eq!(
+            (*Chunk::plus_offset(p, sz + mem::size_of::<usize>())).head,
+            0
+        );
+    }
+
+    unsafe fn check_free_chunk(&self, p: *mut Chunk) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        let sz = Chunk::size(p);
+        let next = Chunk::plus_offset(p, sz);
+        self.check_any_chunk(p);
+        debug_assert!(!Chunk::inuse(p));
+        debug_assert!(!Chunk::pinuse(Chunk::next(p)));
+        debug_assert!(!Chunk::mmapped(p));
+        if p != self.dv && p != self.top {
+            if sz >= self.min_chunk_size() {
+                debug_assert_eq!(align_up(sz, self.malloc_alignment()), sz);
+                debug_assert!(self.is_aligned(Chunk::to_mem(p) as usize));
+                debug_assert_eq!((*next).prev_foot, sz);
+                debug_assert!(Chunk::pinuse(p));
+                debug_assert!(next == self.top || Chunk::inuse(next));
+                debug_assert_eq!((*(*p).next).prev, p);
+                debug_assert_eq!((*(*p).prev).next, p);
+            } else {
+                debug_assert_eq!(sz, mem::size_of::<usize>());
+            }
+        }
+    }
+
+    unsafe fn check_malloc_state(&mut self) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        for i in 0..NSMALLBINS {
+            self.check_smallbin(i as u32);
+        }
+        for i in 0..NTREEBINS {
+            self.check_treebin(i as u32);
+        }
+        if self.dvsize != 0 {
+            self.check_any_chunk(self.dv);
+            debug_assert_eq!(self.dvsize, Chunk::size(self.dv));
+            debug_assert!(self.dvsize >= self.min_chunk_size());
+            let dv = self.dv;
+            debug_assert!(!self.bin_find(dv));
+        }
+        if !self.top.is_null() {
+            self.check_top_chunk(self.top);
+            debug_assert!(self.topsize > 0);
+            let top = self.top;
+            debug_assert!(!self.bin_find(top));
+        }
+        let total = self.traverse_and_check();
+        debug_assert!(total <= self.footprint);
+        debug_assert!(self.footprint <= self.max_footprint);
+    }
+
+    unsafe fn check_smallbin(&mut self, idx: u32) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        let b = self.smallbin_at(idx);
+        let mut p = (*b).next;
+        let empty = self.smallmap & (1 << idx) == 0;
+        if p == b {
+            debug_assert!(empty)
+        }
+        if !empty {
+            while p != b {
+                let size = Chunk::size(p);
+                self.check_free_chunk(p);
+                debug_assert_eq!(self.small_index(size), idx);
+                debug_assert!((*p).next == b || Chunk::size((*p).next) == Chunk::size(p));
+                let q = Chunk::next(p);
+                if (*q).head != Chunk::fencepost_head() {
+                    self.check_inuse_chunk(q);
+                }
+                p = (*p).next;
+            }
+        }
+    }
+
+    unsafe fn check_treebin(&mut self, idx: u32) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        let tb = self.treebin_at(idx);
+        let t = *tb;
+        let empty = self.treemap & (1 << idx) == 0;
+        if t.is_null() {
+            debug_assert!(empty);
+        }
+        if !empty {
+            self.check_tree(t);
+        }
+    }
+
+    unsafe fn check_tree(&mut self, t: *mut TreeChunk) {
+        if !cfg!(debug_assertions) {
+            return;
+        }
+        let tc = TreeChunk::chunk(t);
+        let tindex = (*t).index;
+        let tsize = Chunk::size(tc);
+        let idx = self.compute_tree_index(tsize);
+        debug_assert_eq!(tindex, idx);
+        debug_assert!(tsize >= self.min_large_size());
+        debug_assert!(tsize >= self.min_size_for_tree_index(idx));
+        debug_assert!(idx == NTREEBINS as u32 - 1 || tsize < self.min_size_for_tree_index(idx + 1));
+
+        let mut u = t;
+        let mut head = ptr::null_mut::<TreeChunk>();
+        loop {
+            let uc = TreeChunk::chunk(u);
+            self.check_any_chunk(uc);
+            debug_assert_eq!((*u).index, tindex);
+            debug_assert_eq!(Chunk::size(uc), tsize);
+            debug_assert!(!Chunk::inuse(uc));
+            debug_assert!(!Chunk::pinuse(Chunk::next(uc)));
+            debug_assert_eq!((*(*uc).next).prev, uc);
+            debug_assert_eq!((*(*uc).prev).next, uc);
+            let left = (*u).child[0];
+            let right = (*u).child[1];
+            if (*u).parent.is_null() {
+                debug_assert!(left.is_null());
+                debug_assert!(right.is_null());
+            } else {
+                debug_assert!(head.is_null());
+                head = u;
+                debug_assert!((*u).parent != u);
+                debug_assert!(
+                    (*(*u).parent).child[0] == u
+                        || (*(*u).parent).child[1] == u
+                        || *((*u).parent as *mut *mut TreeChunk) == u
+                );
+                if !left.is_null() {
+                    debug_assert_eq!((*left).parent, u);
+                    debug_assert!(left != u);
+                    self.check_tree(left);
+                }
+                if !right.is_null() {
+                    debug_assert_eq!((*right).parent, u);
+                    debug_assert!(right != u);
+                    self.check_tree(right);
+                }
+                if !left.is_null() && !right.is_null() {
+                    debug_assert!(
+                        Chunk::size(TreeChunk::chunk(left)) < Chunk::size(TreeChunk::chunk(right))
+                    );
+                }
+            }
+
+            u = TreeChunk::prev(u);
+            if u == t {
+                break;
+            }
+        }
+        debug_assert!(!head.is_null());
+    }
+
+    fn min_size_for_tree_index(&self, idx: u32) -> usize {
+        let idx = idx as usize;
+        (1 << ((idx >> 1) + TREEBIN_SHIFT)) | ((idx & 1) << ((idx >> 1) + TREEBIN_SHIFT - 1))
+    }
+
+    unsafe fn bin_find(&mut self, chunk: *mut Chunk) -> bool {
+        let size = Chunk::size(chunk);
+        if self.is_small(size) {
+            let sidx = self.small_index(size);
+            let b = self.smallbin_at(sidx);
+            if !self.smallmap_is_marked(sidx) {
+                return false;
+            }
+            let mut p = b;
+            loop {
+                if p == chunk {
+                    return true;
+                }
+                p = (*p).prev;
+                if p == b {
+                    return false;
+                }
+            }
+        } else {
+            let tidx = self.compute_tree_index(size);
+            if !self.treemap_is_marked(tidx) {
+                return false;
+            }
+            let mut t = *self.treebin_at(tidx);
+            let mut sizebits = size << leftshift_for_tree_index(tidx);
+            while !t.is_null() && Chunk::size(TreeChunk::chunk(t)) != size {
+                t = (*t).child[(sizebits >> (mem::size_of::<usize>() * 8 - 1)) & 1];
+                sizebits <<= 1;
+            }
+            if t.is_null() {
+                return false;
+            }
+            let mut u = t;
+            let chunk = chunk as *mut TreeChunk;
+            loop {
+                if u == chunk {
+                    return true;
+                }
+                u = TreeChunk::prev(u);
+                if u == t {
+                    return false;
+                }
+            }
+        }
+    }
+
+    unsafe fn traverse_and_check(&self) -> usize {
+        0
+    }
+}
+
+const PINUSE: usize = 1 << 0;
+const CINUSE: usize = 1 << 1;
+const FLAG4: usize = 1 << 2;
+const INUSE: usize = PINUSE | CINUSE;
+const FLAG_BITS: usize = PINUSE | CINUSE | FLAG4;
+
+impl Chunk {
+    unsafe fn fencepost_head() -> usize {
+        INUSE | mem::size_of::<usize>()
+    }
+
+    unsafe fn size(me: *mut Chunk) -> usize {
+        (*me).head & !FLAG_BITS
+    }
+
+    unsafe fn next(me: *mut Chunk) -> *mut Chunk {
+        (me as *mut u8).offset(((*me).head & !FLAG_BITS) as isize) as *mut Chunk
+    }
+
+    unsafe fn prev(me: *mut Chunk) -> *mut Chunk {
+        (me as *mut u8).offset(-((*me).prev_foot as isize)) as *mut Chunk
+    }
+
+    unsafe fn cinuse(me: *mut Chunk) -> bool {
+        (*me).head & CINUSE != 0
+    }
+
+    unsafe fn pinuse(me: *mut Chunk) -> bool {
+        (*me).head & PINUSE != 0
+    }
+
+    unsafe fn clear_pinuse(me: *mut Chunk) {
+        (*me).head &= !PINUSE;
+    }
+
+    unsafe fn inuse(me: *mut Chunk) -> bool {
+        (*me).head & INUSE != PINUSE
+    }
+
+    unsafe fn mmapped(me: *mut Chunk) -> bool {
+        (*me).head & INUSE == 0
+    }
+
+    unsafe fn set_inuse(me: *mut Chunk, size: usize) {
+        (*me).head = ((*me).head & PINUSE) | size | CINUSE;
+        let next = Chunk::plus_offset(me, size);
+        (*next).head |= PINUSE;
+    }
+
+    unsafe fn set_inuse_and_pinuse(me: *mut Chunk, size: usize) {
+        (*me).head = PINUSE | size | CINUSE;
+        let next = Chunk::plus_offset(me, size);
+        (*next).head |= PINUSE;
+    }
+
+    unsafe fn set_size_and_pinuse_of_inuse_chunk(me: *mut Chunk, size: usize) {
+        (*me).head = size | PINUSE | CINUSE;
+    }
+
+    unsafe fn set_size_and_pinuse_of_free_chunk(me: *mut Chunk, size: usize) {
+        (*me).head = size | PINUSE;
+        Chunk::set_foot(me, size);
+    }
+
+    unsafe fn set_free_with_pinuse(p: *mut Chunk, size: usize, n: *mut Chunk) {
+        Chunk::clear_pinuse(n);
+        Chunk::set_size_and_pinuse_of_free_chunk(p, size);
+    }
+
+    unsafe fn set_foot(me: *mut Chunk, size: usize) {
+        let next = Chunk::plus_offset(me, size);
+        (*next).prev_foot = size;
+    }
+
+    unsafe fn plus_offset(me: *mut Chunk, offset: usize) -> *mut Chunk {
+        (me as *mut u8).offset(offset as isize) as *mut Chunk
+    }
+
+    unsafe fn minus_offset(me: *mut Chunk, offset: usize) -> *mut Chunk {
+        (me as *mut u8).offset(-(offset as isize)) as *mut Chunk
+    }
+
+    unsafe fn to_mem(me: *mut Chunk) -> *mut u8 {
+        (me as *mut u8).offset(Chunk::mem_offset())
+    }
+
+    fn mem_offset() -> isize {
+        2 * (mem::size_of::<usize>() as isize)
+    }
+
+    unsafe fn from_mem(mem: *mut u8) -> *mut Chunk {
+        mem.offset(-2 * (mem::size_of::<usize>() as isize)) as *mut Chunk
+    }
+}
+
+impl TreeChunk {
+    unsafe fn leftmost_child(me: *mut TreeChunk) -> *mut TreeChunk {
+        let left = (*me).child[0];
+        if left.is_null() {
+            (*me).child[1]
+        } else {
+            left
+        }
+    }
+
+    unsafe fn chunk(me: *mut TreeChunk) -> *mut Chunk {
+        &mut (*me).chunk
+    }
+
+    unsafe fn next(me: *mut TreeChunk) -> *mut TreeChunk {
+        (*TreeChunk::chunk(me)).next as *mut TreeChunk
+    }
+
+    unsafe fn prev(me: *mut TreeChunk) -> *mut TreeChunk {
+        (*TreeChunk::chunk(me)).prev as *mut TreeChunk
+    }
+}
+
+const EXTERN: u32 = 1 << 0;
+
+impl Segment {
+    unsafe fn is_extern(seg: *mut Segment) -> bool {
+        (*seg).flags & EXTERN != 0
+    }
+
+    unsafe fn can_release_part<A: Allocator>(system_allocator: &A, seg: *mut Segment) -> bool {
+        system_allocator.can_release_part((*seg).flags >> 1)
+    }
+
+    unsafe fn sys_flags(seg: *mut Segment) -> u32 {
+        (*seg).flags >> 1
+    }
+
+    unsafe fn holds(seg: *mut Segment, addr: *mut u8) -> bool {
+        (*seg).base <= addr && addr < Segment::top(seg)
+    }
+
+    unsafe fn top(seg: *mut Segment) -> *mut u8 {
+        (*seg).base.offset((*seg).size as isize)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use System;
+
+    // Prime the allocator with some allocations such that there will be free
+    // chunks in the treemap
+    unsafe fn setup_treemap<A: Allocator>(a: &mut Dlmalloc<A>) {
+        let large_request_size = NSMALLBINS * (1 << SMALLBIN_SHIFT);
+        assert!(!a.is_small(large_request_size));
+        let large_request1 = a.malloc(large_request_size);
+        assert_ne!(large_request1, ptr::null_mut());
+        let large_request2 = a.malloc(large_request_size);
+        assert_ne!(large_request2, ptr::null_mut());
+        a.free(large_request1);
+        assert_ne!(a.treemap, 0);
+    }
+
+    #[test]
+    // Test allocating, with a non-empty treemap, a specific size that used to
+    // trigger an integer overflow bug
+    fn treemap_alloc_overflow_minimal() {
+        let mut a = Dlmalloc::new(System::new());
+        unsafe {
+            setup_treemap(&mut a);
+            let min_idx31_size = (0xc000 << TREEBIN_SHIFT) - a.chunk_overhead() + 1;
+            assert_ne!(a.malloc(min_idx31_size), ptr::null_mut());
+        }
+    }
+
+    #[test]
+    // Test allocating the maximum request size with a non-empty treemap
+    fn treemap_alloc_max() {
+        let mut a = Dlmalloc::new(System::new());
+        unsafe {
+            setup_treemap(&mut a);
+            let max_request_size = a.max_request() - 1;
+            assert_eq!(a.malloc(max_request_size), ptr::null_mut());
+        }
+    }
+}