In _malloc_init(), round up the region being mprotected RW to the malloc
page size, rather than relying upon mprotect to round up to the actual mmu
page size.

This repairs malloc operation on systems where the malloc page size
(1 << _MAX_PAGE_SHIFT) is larger than the mmu page size.

ok otto@

A small cleanup of malloc_bytes(), getting rid of a goto and a tiny
bit of optimization; ok tb@ asou@

Save backtraces to show in leak dump. Depth of backtrace set by
malloc option D (aka 1), 2, 3 or 4. No performance impact if not
used. ok asou@

KNF plus fixed a few signed vs unsigned compares (that we actually
not real problems)

A few micro-optimizations; ok asou@

When option D is active, store callers for all chunks; this avoids
the 0x0 call sites for leak reports. Also display more info on
detected write of free chunks: print the info about where the chunk
was allocated, and for the preceding chunk as well.
ok asou@

Print waring message when not allocated memory in putleakinfo().

ok otto.

Recommit "Allow to ask for deeper callers for leak reports using
malloc options"

Now only enabled for platforms where it's know to work and written
as a inline functions instead of a macro.

Revert previous, not all platforms allow compiling
__builtin_return_address(a) with a != 0.

Allow to ask for deeper callers for leak reports using malloc options.
ok deraadt@

Add portable version and m88k-specific version lb() function, because
unfortunately gcc3 does not have __builtin_clz().

ok miod@ otto@

More thorough write-afetr-free checks.

On free, chunks (the pieces of a pages used for smaller allocations)
are junked and then validated after they leave the delayed free
list. So after free, a chunk always contains junk bytes. This means
that if we start with the right contents for a new page of chunks,
we can *validate* instead of *write* junk bytes when (re)-using a
chunk.

With this, we can detect write-after-free when a chunk is recycled,
not justy when a chunk is in the delayed free list. We do a little
bit more work on initial allocation of a page of chunks and when
re-using (as we validate now even on junk level 1).

Also: some extra consistency checks for recallocaray(3) and fixes
in error messages to make them more consistent, with man page bits.

Plus regress additions.

Remove malloc interposition, a workaround that was once needed for emacs
ok guenther@

As mmap(2) is no longer a LOCK syscall, do away with the extra
unlock-lock dance it serves no real purpose any more. Confirmed
by a small performance increase in tests. ok @tb

remove duplicate include
ok otto@

Dump (leak) info using utrace(2) and compile the code always in
except for bootblocks. This way we have built-in leak detecction
always (if enable by malloc flags). See man pages for details.

Introduce variation in location of junked bytes; ok tb@

Check all chunks in the delayed free list for write-after-free.
Should catch more of them and closer (in time) to the WAF. ok tb@

Change malloc chunk sizes to be fine grained.

The basic idea is simple: one of the reasons the recent sshd bug
is potentially exploitable is that a (erroneously) freed malloc
chunk gets re-used in a different role. malloc has power of two
chunk sizes and so one page of chunks holds many different types
of allocations. Userland malloc has no knowledge of types, we only
know about sizes. So I changed that to use finer-grained chunk
sizes.

This has some performance impact as we need to allocate chunk pages
in more cases. Gain it back by allocation chunk_info pages in a
bundle, and use less buckets is !malloc option S. The chunk sizes
used are 16, 32, 48, 64, 80, 96, 112, 128, 160, 192, 224, 256, 320,
384, 448, 512, 640, 768, 896, 1024, 1280, 1536, 1792, 2048 (and a
few more for sparc64 with its 8k sized pages and loongson with its
16k pages).

If malloc option S (or rather cache size 0) is used we use strict
multiple of 16 sized chunks, to get as many buckets as possible.
ssh(d) enabled malloc option S, in general security sensitive
programs should.

See the find_bucket() and bin_of() functions. Thanks to Tony Finch
for pointing me to code to compute nice bucket sizes.

ok tb@

There is no reason to-be-cleared chunks cannot participate in delayed
freeing; ok tb@

Change the way malloc_init() works so that the main data structures
can be made immutable to provide extra protection. Also init pools
on-demand: only pools that are actually used are initialized.

Tested by many

put the malloc_readonly struct into the "openbsd.mutable" section, so
that the kernel and ld.so will know not to mark it immutable. malloc
handles the read/write transitions by itself.

To figure our whether a large allocation can be grown into the
following page(s) we've been first mquery()ing for it, mmapp()ing
w/o MAP_FIXED if available, and then munmap()ing if there was a
race. Instead, just try it directly with
mmap(MAP_FIXED | __MAP_NOREPLACE)

tested in snaps for weeks

ok deraadt@

Currently malloc caches a number of free'ed regions up to 128k
in size. This cache is indexed by size (in # of pages), so it is
very quick to check. Some programs allocate and deallocate larger
allocations in a frantic way. Accomodate those programs by also
keeping a cache of regions between 128k and 2M, in a cache of variable
sized regions.

Tested by many in snaps; ok deraadt@

Switch two calls from memset() to explicit_bzero()

This matches the documented behavior more obviously and ensures that
these aren't optimized away, although this is unlikely.

Discussed with deraadt and otto

Make MALLOC_STATS compile again; noted by Omar Polo and Joe Nelson

An extra internal consistency check and a missing stats adjustment. ok tb@

Change the implementation of the malloc cache to keep lists of
regions of a given size. In snaps for a while, committing since
no issues were reported and a wider audience is good. ok deraadt@

- Make use of the fact that we know how the chunks are aligned, and
write 8 bytes at the time by using a uint64_t pointer. For an
allocation a max of 4 such uint64_t's are written spread over the
allocation. For pages sized and larger, the first page is junked in
such a way.
- Delayed free of a small chunk checks the corresponiding way.
- Pages ending up in the cache are validated upon unmapping or re-use.
In snaps for a while

mapalign() only handles allocations >= a page; problem found by and ok semarie@

make fixed-sized fixed-value mib[] arrays be const
ok guenther tb millert

As noted by tb@ previous commit only removed an unused fucntion.
So redo previous commit properly:
Use random value for canary bytes; ok tb@.

Use random value for canary bytes; ok tb@

For page-sized and larger allocations do not put the pages we're
shaving off into the cache but unamp them. Pages in the cache get
re-used and then a future grow of the first allocation will be
hampered. Also make realloc a no-op for small shrinkage.
ok deraadt@

When system calls indicate an error they return -1, not some arbitrary
value < 0. errno is only updated in this case. Change all (most?)
callers of syscalls to follow this better, and let's see if this strictness
helps us in the future.

Only override size of chunk if we're not given the actual length.
Fixes malloc_conceal...freezero with malloc options C and/or G.

Inroduce malloc_conceal() and calloc_conceal(). Similar to their
counterparts but return memory in pages marked MAP_CONCEAL and on
free() freezero() is actually called.

Move default numer of pools in the multi-threaded case to 8. Various tests
by me and others indicate that it is the optimum.

Make the "not my pool" searching loop a tiny bit smarter, while
making the number of pools variable. Do not document the malloc
conf settings atm, don't know yet if they will stay. Thanks to all
the testers. ok deraadt@

Improve speed for the multi-threaded case by reducing lock contention.
tested by many; ok florian@

style; OK otto

Refactor "find the right pool" code into a function. ok djm@ tb@

Introducing malloc_usable_size() was a mistake. While some other
libs have it, it is a function that is considered harmful, so:

Delete malloc_usable_size(). It is a function that blurs the line
between malloc managed memory and application managed memory and
exposes some of the internal workings of malloc. If an application
relies on that, it is likely to break using another implementation
of malloc. If you want usable size x, just allocate x bytes. ok
deraadt@ and other devs

Fix compilation on alpha, where DEF_WEAK() really must be paired with
PROTO_NORMAL(). Problem noted by deraadt@

Implement malloc_usable_size(); ok millert@ deraadt@ and jmc@ for the man page

Use the new vm.malloc_conf sysctl; ok millert@ deraadt@

Implement C11's aligned_alloc(3). ok guenther@

sys/uio.h is not used anymore

fix MALLOC_STATS; spotted by and ok semarie@

use _ALIGN() which is uhm a bit OpenBSD-specific, but it means we
don't need to use sys/param.h at all, guess which one i believe is
greater namespace polution
ok otto

Use _MAX_PAGE_SHIFT, rather than #ifdef mips64
ok guenther kettenis

use consistent style for for loop in unmap(), no functional change

keep in sync with ld.so malloc.c

- An error in the multithreaded case could print the wrong function name
- Start with a full page of struct region_info's
- Save an mprotect in the init code: allocate 3 pages with none and
make the middle page r/w instead of a r/w allocation and two calls to make the
guard pages none

- do not junk pages returned by free_bytes(), all freed chunks are already
junked
- freezero(): only clear requested size

Zap the rotor, it was a wrong idea. Cluebat applied by kshe who
came also up with this diff. Simple, no bias and benchmarks show the extra
random calls disappear in te measurement noise.

Move to ffs(3) for bitmask scanning. I played with this earlier,
but at that time ffs function calls were generated instead of the
compiler inlining the code. Now that ffs is marked protected in
libc this is handled better. Thanks to kshe who prompted me to
look at this again.

optimization and some cleanup; mostly from kshe (except the unmap() part)

Only init chunk_info once, plus some moving of code to group related functions.

step one in avoiding unneccesary init of chunk_info;
some cleanup; tested by sthen@ on a ports build

's' should include 'f'; from Jacqueline Jolicoeur

Restore a return that was inadvertently removed from freezero() in r1.234,
which results in an internal double free when internal functions are not
in use.

ok otto@

do not return f() where f is a void function; loop var type fix

Use dprintf instead of snprintf/write

Make delayed free non-optional and make F do an extensive double free check.
ok tb@ tedu@

mapalign returns MAP_FAILED for failuer; from George Koehler

check double free before canary for chunks; ok millert@

two MALLOC_STATS only tweaks; one from David CARLIER, the other found by clang

one more instance of the previous commit; also initialize ->offset to a
definite value in the size == 0 case

Only access offset if canaries are enabled *and* size > 0, otherwise offset
is not initialized. Problem spotted by Carlin Bingham; ok phessler@ tedu@

port the RBT code to userland by making it part of libc.

src/lib/libc/gen/tree.c is a copy of src/sys/kern/subr_tree.c, but with
annotations for symbol visibility. changes to one should be reflected
in the other.

the malloc debug code that uses RB code is ported to RBT.

because libc provides the RBT code, procmap doesn't have to reach into
the kernel and build subr_tree.c itself now.

mild enthusiasm from many
ok guenther@

- fix bug wrt posix_memalign(3) of blocks between half a page and a page
- document posix_memalign() does not play nice with reacallocarray(3) and
freezero(3)

For small allocations (chunk) freezero only validates the given
size if canaries are enabled. In that case we have the exact requested
size of the allocation. But we can at least check the given size
against the chunk size if C is not enabled. Plus add some braces
so my brain doesn't have to scan for dangling else problems when I
see this code.

don't forget to fill in canary bytes for posix_memalign(3); reported by
and ok jeremy@

whitespace fixes

allow clearing less than allocated and document freezero(3) better

Introducing freezero(3) a version of free that guarantees the process
no longer has access to the content of a memmory object. It does
this by either clearing (if the object memory remains cached) or
by calling munmap(2). ok millert@, deraadt@, guenther@

first print size in meta-data then supplied arg size when an inconsistency is
detected wrt recallocarray()

small cleanup & optimization; ok deraadt@ millert@

add a helper function to print all pools #ifdef MALLOC_STATS
from David CARLIER

move recallocarray to malloc.c and
- use internal meta-data to do more consistency checking (especially with
option C)
- use cheap free if possible
ok deraadt@

Add a NULL test to wrterror() to avoid a NULL deref when called from a
free() error path.

ok otto@

fix a comment and rm some dead code as a result of the previous diff

Let realloc handle and produce moved pointers for allocations between
half a page and a page. ok jmatthew@ tb@

1. When shrinking a chunk allocation, compare the size of the current
allocation to the size of the new allocation (instead of the requested size).
2. Previously realloc takes the easy way and always reallocates if C is
active. This commit fixes by carefully updating the recorded requested
size in all cases, and writing the canary bytes in the proper location
after reallocating.
3. Introduce defines to test if MALLOC_MOVE should be done and to
compute the new value.

MALLOC_STATS tweaks, by default not compiled in

small tweak to also check canaries if F is in effect

remove some old option letters and also make P non-settable. It has
been the default for ages, and I see no valid reason to be able to
disable it. ok natano@

Pages in the malloc cache are either reused quickly or unmapped
quickly. In both cases it does not make sense to set hints on them.
So remove that option, which is just a remainder of old times when
malloc used to hold on to pages. ok stefan@

- fix MALLOC_STATS compile
- redundant cast is redundant

fix some void * arithmetic by casting

and recommit with fixed GC

backout for now; flag combination GC is not ok

Also place canaries in > page sized objects (if C is in effect); ok tb@

Wrap _malloc_init() so internal calls go directly

prodded by otto@
ok kettenis@ otto@

0xd0 -> 0xdb; ok deraadt@ millert@ tedu@

optimize canary code a bit by storing offset of sizes table instead of
recomputing it all the time

stray tab

Beter implementation of chunk canaries: store size in chunk meta data
instead of chunk itself; does not change actual allocated size; ok tedu@

Delete casts to off_t and size_t that are implied by assignments
or prototypes. Ditto for some of the char* and void* casts too.

verified no change to instructions on ILP32 (i386) and LP64 (amd64)
ok natano@ abluhm@ deraadt@ millert@

move page junking tp unmap(), right before we stick the region in the cache;
ok tedu@

Less lock contention by using more pools for mult-threaded programs.
tested by many (thanks!) ok tedu, guenther@

black magic for sparc page size can go

wrterror() is fatal, delete dead code; ok tom@ natano@ tedu@

J/j is a three valued option, document and fix code to actuall support that
with a little help from jmc@ for the man page bits
ok jca@ and a reluctant tedu@

adapt S option: add C, rm F (not relevant with 0 cache and disables
chunk rnd), rm P: is default

Back out previous; otto saw a potential race that could lead to a
double unmap and I experienced a much more unstable firefox.

discussed with otto on icb

defer munmap to after unlocking malloc. this can (unfortunately) be an
expensive syscall, and we don't want to tie up other threads. there's no
need to hold the lock, so defer it to afterwards.
from Michael McConville
ok deraadt

two times a define to an inline function, from Michael McConville; ok djm@

tweak MALLOC_STATS printing (switched off by default), prodded by
Michael McConville

redundant memset(3), from Michael McConville, ok armani@

properly guard to macros

ok otto@

small step towards multiple pools: move two globls into the struct dir_info
ok @stefan armani@

environ and __progname are not declared in a public header; declare them
in libc's hidden/stdlib.h instead of in each .c file that needs one

ok deraadt@ gsoares@ mpi@

refactor option letter parsing into a subfunction, to increase clarity
about which options are turned on/off by 's' and 'S'
ok tedu

Don't crash dumping malloc stats if malloc_init hasn't been called, noted by
David CARLIER

Long ago, malloc internally had two kinds of failures, warnings and errors.
The 'A' option elevated warnings to errors, and has been the default for some
time. Then warnings were effectively eliminated in favor of everything
being an error, but then the 'a' flag turned real errors into warnings!
Remove the 'a' option entirely. You shouldn't have used it anyway.
ok tb tdeval

another case where bad things would happen after wrterror

if somebody makes the mistake of disabling abort, don't deref null in
validate_junk. from Michal Mazurek

Integrate two patches originally from Daniel Micay.
1. Optionally add random "canaries" to the end of an allocation. This
requires increasing the internal size of the allocation slightly, which
probably results in a large effective increase with current power of two
sizing. Therefore, this option is only enabled via 'C'.
2. When writing junk (0xdf) to freed chunks (current default behavior),
check that the junk is still intact when finally freeing the delayed chunk
to catch some potential use after free. This should be pretty cheap so
there's no option to control it separately.
ok deraadt tb

For now, permit overriding of the malloc family, to make emacs happy

Wrap <stdlib.h> so that calls go direct and the symbols not in the
C standard are all weak.
Apply __{BEGIN,END}_HIDDEN_DECLS to gdtoa{,imp}.h, hiding the
arch-specific __strtorx, __ULtox_D2A, __strtorQ, __ULtoQ_D2A symbols.

improve realloc. when expanding a region, actually use the free page cache
instead of simply zapping it. this can save many syscalls in a program
that repeatedly grows and shrinks a buffer, as observed in the wild.

Move to the <limits.h> universe.
review by millert, binary checking process with doug, concept with guenther

rename kern enter/exit macros to malloc enter/leave to better reflect
what's going on.

a small tweak to improve malloc in multithreaded programs. we don't need
to hold the malloc lock across mmap syscalls in all cases. dropping it
allows another thread to access the existing chunk cache if necessary.
could be improved to be a bit more aggressive, but i've been testing this
simple diff for some time now with good results.

reduce obvious dependency on global g_pool by moving to local aliases
ok otto

extra evil spaces snuck in over the last while

Move to a smaller rbytes buffer and skip a random part. Not to
improve the random stream itself (it doesn't), but to introduce
noise in the arc4random calling pattern. Thanks to matthew@ who
pointed out bias in a previous diff, ok deraadt@ matthew@

move random bytes buffer to be part of mmaped pages; ok tedu@

move all stats collecting under MALLOC_STATS; ok krw@

fix MALLOC_STATS (not compiled in by default); ok tedu@

factor out a bit of the chunk index code and use it to make sure that a
freed chunk is actually freeable immediately. catch more errors.
hints/ok otto

change to having four freelists per size, to reduce another source of
deterministic behavior. four selected because it's more than three, less
than five. i.e., no particular reason.

fix MALLOC_STATS code that was broken in rev 1.159, not compiled in by default

move reallocarray() to a seperate file so that -portable applications
can avoid reinventing the wheel
ok guenther schwarze

comment style fix

ok crickets@

nibbles aren't enough random, use bytes. does a better job of picking
a free chunk at random and may allow to increase delayed chunk array.
ok otto

remove Z option and default to something halfway to J.
we always junk small chunks now, and the first part of pages,
but only after free. J still does the old thing. j disables everything.
Consider experimental as we evaluate performance in the real world.
ok otto

explain a bit more what's going on for stupid me.
okay otto@

Better, cleaner hash function that computes the same on be and le archs.
Should improve sparc64 and other be archs. ok matthew@ miod@

change mallocarray to reallocarray. useful in a few more situations.
malloc can, as always, be emulated via realloc(NULL).
ok deraadt

Introducing: void *mallocarray(size_t nmemb, size_t size);
Like calloc(), except without the cleared-memory gaurantee
ok beck guenther, discussed for more than a year...

print pid in error messages; ok reyk@

Update Copyright notice; ok otto@ beck@ deraadt@.
This is merely a by-product of figuring out the amount of phk@ code
contained herein; i'm not planning to hack on this file.

Poul-Henning Kamp informed me he is allright with this licensing change.

avoid arithetic on void *
ok guenther otto

Fix bug in random offset introduced in rev 1.143; random range was
expanded, but not enough due to precedence error. Spotted by Thorsten Glaser.

Add a new malloc option 'U' => "Free unmap" that does the guarding/
unmapping of freed allocations without disabling chunk randomisation
like the "Freeguard" ('F') option does. Make security 'S' option
use 'U' and not 'F'.

Rationale: guarding with no chunk randomisation is great for debugging
use-after-free, but chunk randomisation offers better defence against
"heap feng shui" style attacks that depend on carefully constructing a
particular heap layout so we should leave this enabled when requesting
security options.

Fix precedence bug (& has lower precedence than !=).

Okay otto@.

Found by Michal Mazurek <akfaew at jasminek dot net>, thanks!

use PAGE_SHIFT instead of PGSHIFT, in preperation for future
param.h symbol reduction.
ok guenther

after a talk with ariane, use MAP_FIXED for mquery to avoid the cost of
scanning for free space if the hint isn't available.
also, on further inspection, this will prevent pmap_prefer from "improving"
our hint.

two changes which should improve realloc. first, fix zapcacheregion to
clear out the entire requested area, not just a perfect fit. second,
use mquery to check for room to avoid getting an address we don't like
and having to send it back.

two small fixes to free page cache. first, we need two nibbles of random
in order to span the the entire cache. second, on free use the same offset
to put things in the cache instead of always starting at zero.
ok otto

Support larger-than-page-alignment requests in posix_memalign() by
overallocating and then releasing unneeded memory pages.

ok otto

- Test for the retrieved page address not being NULL. This turns free((void*)1)
into an bogus pointer error instead of a segfault.
- Document that we use the assumption that a non-MAP_FIXED mmap() with
hint 0 never returns NULL.

Make struct chunk_info a variable sized struct, wasting less
space for meta data by only allocating space actually needed for
the bitmap (modulo alignment requirements). ok deraadt@

on malloc flag S, set cache size to 0; will catch even more
use-after-free bugs; ok krw@ dlg@ pirofti@

as man page states, lower case undoes upper case. add support for little s,
no security, for consistency. use of this option is discouraged. :)
ok deraadt guenther millert

save errno dance in wrterror() and malloc_dump(); prompted by and ok deraadt@

introduce symbolic constant for initial number of regions

zap regions_bits and rework MALLOC_MAXSHIFT a bit; ok djm@

Avoid fp computations for stats, this make calling malloc_dump() safe in more
cases.

fix comment, the bitmap is an array of u_short now

Introduce leak detection code for MALLOC_STATS

Move MALLOC_STATS code to bottom of file, so the real stuff is more at the top.

Up until now, malloc scanned the bits of the chunk bitmap from
position zero, skipping a random number of free slots and then
picking the next free one. This slowed things down, especially if
the number of full slots increases.

This changes the scannning to start at a random position in the
bitmap and then taking the first available free slot, wrapping if
the end of the bitmap is reached. Of course we'll still scan more
if the bitmap becomes more full, but the extra iterations skipping
free slots and then some full slots are avoided.

The random number is derived from a global, which is incremented
by a few random bits every time a chunk is needed (with a small optimization
if only one free slot is left).

Thanks to the testers!

Now that we use an array of u_short for the chunk bitmap change a few
1UL to 1U.

More efficient scanning for free chunks while not losing any randomization;
thanks to all testers.

avoid pointer arithmetic on void *

tested for a while by me.

ok otto@

print the pointer value that caused the error (if available); ok
deraadt@ nicm@ (on an earlier version)

add posix_madvise, posix_memalign, strndup, and strnlen. mostly from
brad and millert, with hints from guenther, jmc, and otto I think.
ok previous.

New options 'S', as a shorthand for the options most suitable as an
extra safeguard (FGJ). Idea from deraadt@; ok deraadt@ dlg@

save calls to arc4random() by using a nibble at a time; not because
arc4random() is slow, but it induces getpid() calls; also saves a
bit on stirring efforts

Make userland malloc use __LDPGSZ granularity on mips, regardless of the
actual kernel page size.

Switch the chunk_info lists to doubly-linked lists and use the queue
macros for them. Avoids walking the lists and greatly enhances speed
of freeing chunks in reverse or random order at the cost of a little
space. Suggested by Fabien Romano and Jonathan Armani; ok djm@

Don't forget to fill region from the cache with junk if needed in one case;
from Fabien Romano and Jonathan Armani

No need to clear a mmapped region; from Fabien Romano and Jonathan
Armani

permit -DMALLOC_STATS to compile again
noticed by Jonathan Armani & Fabien Romano
ugh+ok otto@

Check mmap return value against MAP_FAILED not NULL.

Okay deraadt@, otto@.

quieten compiler by converting pointers to uintptr_t before truncating them
to u_int32_t to do integer math with (in a situation where that is legit)
ok otto millert

reintroduce extra malloc protections, but avoiding the use of
PAGE_(SIZE|SHIFT|MASK) defines that evaluate to variables on the
sparc architecture;
ok otto@ tested on my reanimated ss20

PAGE_SIZE is not a valid symbol to use in that way. In particular,
on sparc, it expands to something that just plain does not work,
because the page size can be variable. Sorry we didn't spot this
before. Backing it all out to allow sparc to build; please find a
different way to fix it.

Remove mprotecting of struct dir_info introduced in previous commit
(MALLOC_OPTIONS=L). It was too slow to turn on by default, and we
don't do optional security.

requested by deraadt@ grumbling ok otto@

extra paranoia for malloc(3):

Move all runtime options into a structure that is made read-only
(via mprotect) after initialisation to protect against attacks that
overwrite options to turn off malloc protections (e.g. use-after-free)

Allocate the main bookkeeping data (struct dir_info) using mmap(),
thereby giving it an unpredictable address. Place a PROT_NONE guard
page on either side to further frustrate attacks on it.

Add a new 'L' option that maps struct dir_info PROT_NONE except when
in the allocator code itself. Makes attacks on it basically impossible.

feedback tedu deraadt otto canacar
ok otto

shave off more bytes than you expect by declaring a few const local arrays
as static const

move allocations between half a page and a page as close to the end of
the page as possible (i.e. make malloc option P a default).
ok art@ millert@ krw@

Reduce the leeway malloc allows when moving allocations to the end of
a page to 0. P default will be changed in a separate commit.
ok millert@ art@ krw@

To allow for easier playing with more strict settings introduce
a separate symbolic constant for the leeway we allow when moving
allocations towards the end of a page. No functional change.

avoid a few strlen calls for constant strings; prompted by tg; ok djm@

if the freeprot flag (F) is set, do not do delayed frees for chunks
(might catch errors closer to the trouble spot) and junk fill pages just
before reuse instead of immediate (we can't access the page anyway)
since we set PROT_NONE in the F case. ok djm@

remove distinction between warnings and errors, ok deraadt@ djm@

if MALLOC_STATS is defined, record how many "cheap reallocs" were
tried and how many actually succeeded.

oops, assign errno the right way. caught by david running regress tests

reduce rbyte cache to 512 bytes, no measurable slowdown (even in the
threaded case) but much smaller working set; prompted by and ok deraadt@

save and restore errno on success. while it is not stricly needed for
non-syscalls, there's just too much code not doing the right thing on
error paths; prompted by and ok deraadt@

when increasing the size of a larger than a page allocation try
mapping the region next to the existing one first; there's a pretty
high chance there's a hole there we can use; ok deraadt@ tedu@

avoid spitting up regions when purging stuff from the cache, it puts
too much pressure on the amaps. ok tedu@ deraadt@

Make all combinations of G, P, J and zero-fill work with as little
effort as possible in most cases; ok djm@

unbreak MALLOC_OPTIONS=G that I broke in my last commit;
slightly kludgey solution for until otto fixes it properly; ok otto@

fix calloc() for MALLOC_OPTIONS=J case: SOME_JUNK was being filled into
the freshly mmaped pages disrupting their pure zeroness;
ok otto@ deraadt@

make sure we always map and unmap multiples of MALLOC_PAGESIZE;
case spotted by beck, one by me; ok deraadt@ beck@

Smarter implementation of calloc(3), which uses the fact that mmap(2)
returns zero filled pages; remember to replace this function as well if you
provide your own malloc implementation; ok djm@ deraadt@

small cleanup of error/warning strings

Almost complete rewrite of malloc, to have a more efficient data
structure of tracking pages returned by mmap(). Lots of testing by
lots of people, thanks to you all.
ok djm@ (for a slighly earlier version) deraadt@

remove _MALLOC_LOCK_INIT; major bump; ok deraadt@

remove recalloc(3); it is buggy and impossible to repair without big
costs; ok jmc@ for the man page bits; ok millert@ deraadt@

Use arc4random_buf() when requesting more than a single word of output

Use arc4random_uniform() when the desired random number upper bound
is not a power of two

ok deraadt@ millert@

use pgfree pool like other code does to reserve free list slots.
prevents a few "cannot free mem because i need mem to free mem"
scenarios (one found by weingart@). ok weingart@ millert@ miod@

add recaloc(3)

get cheaper random bytes, less waste and no getpid() calls, which are
done by arc4random(); ok millert@ deraadt@

a failed mmap returns MAP_FAILED, not NULL. found while exercising pax
in low-mem conditions; ok dim@

respond to ben hawkes's ruxcon presentation.
create special allocators for pginfo and pgfree structs instead of imalloc.
this keeps them separated from application memory.
for chunks, to prevent deterministic reuse, keep a small array
and swizzle the to be freed chunk with a random previously freed chunk.
this last bit only for chunks because keeping arbitrarily large regions
of pages around may cause out of memory issues (and pages are, to some
extent, returned in random order).
all changes enabled by default.
thanks to ben for pointing out these issues.
ok tech@

Fix the second malloc_ulimit regression: maintaining the free list
requires memory; try to make sure we have it. If all fails, leak
instead of crash. Test case originally found by cloder@, fix tested
by many.

Do not leave an hole in the directory list if allocation of the
region succeeds, but allocation a required page dir failed. This
can happen if we're really close to ulimit after allocation the
region of the size requested. See malloc_ulimit1 regress test.
Tested by many; thanks.

delint; original from deraadt@ with fixes from tdeval@ and me;
tested by quite a few developers. ok deraadt@

quick path for free(0)
`looks to be safe' millert, okay tedu.

Remove a few warnings. Those were not apparent thanks to a bug in gcc 2.95.

Patch by Leonardo Chiquitto Filho <leonardo@iken.com.br>
Thanks.

further knf and cleaning; ok tdeval

first KNF (no binary diffs)

zap remaining rcsid.

Kill old files that are no longer compiled.

okay theo

Fix the unmapping of freed pages, leaving just 64k worth of cache pages.
Prodded by art@ and fgsch@, ok deraadt@

adding pointer protection to 'G' was too heavyweight. Since malloc guard
should be generally usable, split this out into option 'P'. ok deraadt

handle sizeof(void *) allocations specially when using malloc guard.
they get a whole page and go right at the end of it. ok deraadt tdeval

MMAP(2) malloc, here we go again.

Back out to brk(2) version.

The mmap(2) code is cool and it has already uncovered some bugs in other code.
But some issues remain on some archs, and we can't afford that for production.

Don't worry, it will be back soon... I'll make sure of it...

- Remove the userland data limit check. It's mmap(2)'s job.
- When malloc_abort==0 (MALLOC_OPTIONS=a), don't abort in wrterror().

fine deraadt@

Missing check for NULL.

After a long gestation period, here comes our custom version of malloc(3)
using mmap(2) instead of sbrk(2).
To make a long story short, using mmap(2) in malloc(3) allows us to draw
all the benefits from our mmap(2)'s randomization feature, closing the
effort we did for returning memory blocks from random addresses.

Tested for a long time by many, thanks to them.
Go for it ! deraadt@

Clean up malloc_active state when aborting.
This allows for safe abort handling, without tripping into
false recursivity problems.

Ok tedu@, deraadt@

Sanity fix.
reviewed by deraadt@, tedu@

only whine about recursion once, so we don't get into problems with loops.

by popular demand, malloc guard pages. insert an unreadable/unwriteable
page after each page size allocation to detect overrun. this is
somewhat electric fence like, while attempting to be mostly usable in
production. also, use tdeval's chunk randomization code.
enabled with the G option.
ok deraadt and co.

abort on errors by default. workaround so running out of memory isn't
actually an error, A still applies full effect.
suggested by phk. ok deraadt@ tdeval@

two minor fixes. set errno on recursive calls. ENOMEM suggested by marc@.
lock before setting malloc_func, not after.
ok cloder@ deraadt@

full stop. reverse course. remove all periods, so as to be aligned
with error messages elsewhere. requested ok deraadt@ henning@

remove register. end all sentences with periods.
ok deraadt@ henning@ millert@

ansify function arguments

ok tdeval@

- just warn in case of mmap/brk failure
- extend_pgdir and malloc_make_chunks return int, not void*

ok tedu@

Fix two cases where malloc() returns NULL but does not set errno to ENOMEM.
ok tdeval@ henning@ millert@

Unbreak 64-bit archs...

Pointer cleaning. ok ian@, tedu@, krw@

Add sanity check to prevent int oflow for very large allocations.
Also fix a signed vs. unsigned issue while I am at it.
Found by Jim Geovedi. OK deraadt@

Honour malloc_junk ('J') with realloc(3), and fix page_dir shrink update.

Warn if atexit(3) fails. Change some tabs to spaces. Use
STDERR_FILENO instead of 2.

OK millert@

thread safe libc -- 2nd try. OK miod@, millert@
Thanks to miod@ for m68k and vax fixes

back out previous patch.. there are still some vax/m68k issues

libc changes for thread safety. Tested on:
alpha (millert@), i386 (marc@), m68k (millert@ and miod@),
powerpc (drahn@ and dhartmei@), sparc (millert@ and marc@),
sparc64 (marc@), and vax (millert@ and miod@).
Thanks to millert@, miod@, and mickey@ for fixes along the way.

unsigned vs unsigned int

Part one of userland __P removal. Done with a simple regexp with some minor hand editing to make comments line up correctly. Another pass is forthcoming that handles the cases that could not be done automatically.

THREAD_UNLOCK() on error before returning; millert@ ok.

correct an alignment mis-conception for malloc(0) returned regions.
OK deraadt@

remove dangling spaces and tabs

mprotect allocations sized at 0 bytes. This will cause a fault for access
to such, permitting them to be discovered, instead of exploited as the ssh
crc insertion detector was. Idea by theo, written by tdeval.

-1 -> MAP_FAILED

Use madvise(MADV_FREE) to allow the 'h' option.
(the code was already there, just not enabled).

missing THREAD_UNLOCK; netch@segfault.kiev.ua

typo fix; halogen@nol.net

calloc() needs to be separate from malloc in case a user wants to have
their own malloc() implementation.

Move calloc() into malloc.c and only zero out the area if malloc()
didn't do so for us. By default, malloc() zeros out the space it
allocates but the programmer cannot rely on this as it is implementation-
specific (and configurable via /etc/malloc.conf)

use writev() where possible

wrong ret type for write define (millert@)

malloc can't use write() if it fails very early, so use the unwrapped syscall _thread_sys_write() if we are threaded

Add thread-safety to libc, so that libc_r will build (on i386 at least).
All POSIX libc api now there (to P1003.1c/D10)
(more md stuff is needed for other libc/arch/*)
(setlogin is no longer a special syscall)
Add -pthread option to gcc (that makes it use -lc_r and -D_POSIX_THREADS).
Doc some re-entrant routines
Add libc_r to intro(3)
dig() uses some libc srcs and an extra -I was needed there.
Add more md stuff to libc_r.
Update includes for the pthreads api
Update libc_r TODO

Don't enumerate every arch in the #if since all OpenBSD platforms use the same values for malloc_pageshift and malloc_minsize except for sparc

Oh fun, mucking about with files used on all archs.

This is one of many places in the source that have
#if defined("list all architectures")
Is there some possible way to eliminate, reduce these or at least
have a file that describes all occurrances so that when a new port is
done this could be addressed. like the recent hppa port, does it need to
take a look at this????

make mmap() return void *, add MAP_FAILED

Change realloc(foo,0) to behave like malloc(0). Both now return a pointer
to an object of size zero. This will allow testing on reallocs return value
to determine if the operation was successful or not.

malloc_init() should try to not modify errno

Use MALLOC_EXTRA_SANITY consistently (EXTRA_SANITY was used in many places)
sizeof *pt -> sizeof *px (point to same type of struct but looked wrong).

Make it possible to not output warnings (errors causing aborts are always
output).

Add x/X option to behave like X11 xmalloc; from FreeBSD
Reduce diffs wrt. FreeBSD some

Be more careful with mixing types

Check for overflow; from FreeBSD

is we were set[ug]id an unitialized ptr bit us

Make this 64-bit safe again

Integrate latest malloc(3) from FreeBSD

more 64bit fixes

64 bit clean

removed plus sign from start of line

Make sure we don't dereference stray pointer when running suid or sgid

Restore check for suid / sgid

Latest changes from FreeBSD

From FreeBSD:
> Fix a very rare error condition: The code to free VM back to the kernel
> as done after a quasi-recursive call to free() had modified what we
> thought we knew about the last chunk of pages.
> This bug manifested itself when I did a "make obj" from src/usr.sbin/lpr,
> then make would coredump in the lpd directory.

Avoid pulling in stdio

Remove dead code
Remove unused variables
Silence some warnings
lint(1) is your friend

only support MALLOC_OPTIONS for non-setuid

asm -> __asm, clean lint(1) warnings

Move cfree(3) weak symbol into a seperate file

Make the binding cfree() -> free() weak if possible

Remove ANSI function delcarations and add a cfree() stub function.

Fix RCS ids
Make sure everything uses {SYS,}LIBC_SCCS properly

malloc(3) implementation from FreeBSD; uses mmap(2) to get memory

Add prototypes for internal functions
Change inline to __inline

realloc(ptr, 0) does not free; from seebs@taniemarie.solon.com;
netbsd pr#1806

branches: 1.1.1;
Initial revision

A small cleanup of malloc_bytes(), getting rid of a goto and a tiny
bit of optimization; ok tb@ asou@

Save backtraces to show in leak dump. Depth of backtrace set by
malloc option D (aka 1), 2, 3 or 4. No performance impact if not
used. ok asou@

KNF plus fixed a few signed vs unsigned compares (that we actually
not real problems)

A few micro-optimizations; ok asou@

When option D is active, store callers for all chunks; this avoids
the 0x0 call sites for leak reports. Also display more info on
detected write of free chunks: print the info about where the chunk
was allocated, and for the preceding chunk as well.
ok asou@

Print waring message when not allocated memory in putleakinfo().

ok otto.

Recommit "Allow to ask for deeper callers for leak reports using
malloc options"

Now only enabled for platforms where it's know to work and written
as a inline functions instead of a macro.

Revert previous, not all platforms allow compiling
__builtin_return_address(a) with a != 0.

Allow to ask for deeper callers for leak reports using malloc options.
ok deraadt@

Add portable version and m88k-specific version lb() function, because
unfortunately gcc3 does not have __builtin_clz().

ok miod@ otto@

More thorough write-afetr-free checks.

On free, chunks (the pieces of a pages used for smaller allocations)
are junked and then validated after they leave the delayed free
list. So after free, a chunk always contains junk bytes. This means
that if we start with the right contents for a new page of chunks,
we can *validate* instead of *write* junk bytes when (re)-using a
chunk.

With this, we can detect write-after-free when a chunk is recycled,
not justy when a chunk is in the delayed free list. We do a little
bit more work on initial allocation of a page of chunks and when
re-using (as we validate now even on junk level 1).

Also: some extra consistency checks for recallocaray(3) and fixes
in error messages to make them more consistent, with man page bits.

Plus regress additions.

Remove malloc interposition, a workaround that was once needed for emacs
ok guenther@

As mmap(2) is no longer a LOCK syscall, do away with the extra
unlock-lock dance it serves no real purpose any more. Confirmed
by a small performance increase in tests. ok @tb

remove duplicate include
ok otto@

Dump (leak) info using utrace(2) and compile the code always in
except for bootblocks. This way we have built-in leak detecction
always (if enable by malloc flags). See man pages for details.

Introduce variation in location of junked bytes; ok tb@

Check all chunks in the delayed free list for write-after-free.
Should catch more of them and closer (in time) to the WAF. ok tb@

Change malloc chunk sizes to be fine grained.

The basic idea is simple: one of the reasons the recent sshd bug
is potentially exploitable is that a (erroneously) freed malloc
chunk gets re-used in a different role. malloc has power of two
chunk sizes and so one page of chunks holds many different types
of allocations. Userland malloc has no knowledge of types, we only
know about sizes. So I changed that to use finer-grained chunk
sizes.

This has some performance impact as we need to allocate chunk pages
in more cases. Gain it back by allocation chunk_info pages in a
bundle, and use less buckets is !malloc option S. The chunk sizes
used are 16, 32, 48, 64, 80, 96, 112, 128, 160, 192, 224, 256, 320,
384, 448, 512, 640, 768, 896, 1024, 1280, 1536, 1792, 2048 (and a
few more for sparc64 with its 8k sized pages and loongson with its
16k pages).

If malloc option S (or rather cache size 0) is used we use strict
multiple of 16 sized chunks, to get as many buckets as possible.
ssh(d) enabled malloc option S, in general security sensitive
programs should.

See the find_bucket() and bin_of() functions. Thanks to Tony Finch
for pointing me to code to compute nice bucket sizes.

ok tb@

There is no reason to-be-cleared chunks cannot participate in delayed
freeing; ok tb@

Change the way malloc_init() works so that the main data structures
can be made immutable to provide extra protection. Also init pools
on-demand: only pools that are actually used are initialized.

Tested by many

put the malloc_readonly struct into the "openbsd.mutable" section, so
that the kernel and ld.so will know not to mark it immutable. malloc
handles the read/write transitions by itself.

To figure our whether a large allocation can be grown into the
following page(s) we've been first mquery()ing for it, mmapp()ing
w/o MAP_FIXED if available, and then munmap()ing if there was a
race. Instead, just try it directly with
mmap(MAP_FIXED | __MAP_NOREPLACE)

tested in snaps for weeks

ok deraadt@

Currently malloc caches a number of free'ed regions up to 128k
in size. This cache is indexed by size (in # of pages), so it is
very quick to check. Some programs allocate and deallocate larger
allocations in a frantic way. Accomodate those programs by also
keeping a cache of regions between 128k and 2M, in a cache of variable
sized regions.

Tested by many in snaps; ok deraadt@

Switch two calls from memset() to explicit_bzero()

This matches the documented behavior more obviously and ensures that
these aren't optimized away, although this is unlikely.

Discussed with deraadt and otto

Make MALLOC_STATS compile again; noted by Omar Polo and Joe Nelson

An extra internal consistency check and a missing stats adjustment. ok tb@

Change the implementation of the malloc cache to keep lists of
regions of a given size. In snaps for a while, committing since
no issues were reported and a wider audience is good. ok deraadt@

- Make use of the fact that we know how the chunks are aligned, and
write 8 bytes at the time by using a uint64_t pointer. For an
allocation a max of 4 such uint64_t's are written spread over the
allocation. For pages sized and larger, the first page is junked in
such a way.
- Delayed free of a small chunk checks the corresponiding way.
- Pages ending up in the cache are validated upon unmapping or re-use.
In snaps for a while

mapalign() only handles allocations >= a page; problem found by and ok semarie@

make fixed-sized fixed-value mib[] arrays be const
ok guenther tb millert

As noted by tb@ previous commit only removed an unused fucntion.
So redo previous commit properly:
Use random value for canary bytes; ok tb@.

Use random value for canary bytes; ok tb@

For page-sized and larger allocations do not put the pages we're
shaving off into the cache but unamp them. Pages in the cache get
re-used and then a future grow of the first allocation will be
hampered. Also make realloc a no-op for small shrinkage.
ok deraadt@

When system calls indicate an error they return -1, not some arbitrary
value < 0. errno is only updated in this case. Change all (most?)
callers of syscalls to follow this better, and let's see if this strictness
helps us in the future.

Only override size of chunk if we're not given the actual length.
Fixes malloc_conceal...freezero with malloc options C and/or G.

Inroduce malloc_conceal() and calloc_conceal(). Similar to their
counterparts but return memory in pages marked MAP_CONCEAL and on
free() freezero() is actually called.

Move default numer of pools in the multi-threaded case to 8. Various tests
by me and others indicate that it is the optimum.

Make the "not my pool" searching loop a tiny bit smarter, while
making the number of pools variable. Do not document the malloc
conf settings atm, don't know yet if they will stay. Thanks to all
the testers. ok deraadt@

Improve speed for the multi-threaded case by reducing lock contention.
tested by many; ok florian@

style; OK otto

Refactor "find the right pool" code into a function. ok djm@ tb@

Introducing malloc_usable_size() was a mistake. While some other
libs have it, it is a function that is considered harmful, so:

Delete malloc_usable_size(). It is a function that blurs the line
between malloc managed memory and application managed memory and
exposes some of the internal workings of malloc. If an application
relies on that, it is likely to break using another implementation
of malloc. If you want usable size x, just allocate x bytes. ok
deraadt@ and other devs

Fix compilation on alpha, where DEF_WEAK() really must be paired with
PROTO_NORMAL(). Problem noted by deraadt@

Implement malloc_usable_size(); ok millert@ deraadt@ and jmc@ for the man page

Use the new vm.malloc_conf sysctl; ok millert@ deraadt@

Implement C11's aligned_alloc(3). ok guenther@

sys/uio.h is not used anymore

fix MALLOC_STATS; spotted by and ok semarie@

use _ALIGN() which is uhm a bit OpenBSD-specific, but it means we
don't need to use sys/param.h at all, guess which one i believe is
greater namespace polution
ok otto

Use _MAX_PAGE_SHIFT, rather than #ifdef mips64
ok guenther kettenis

use consistent style for for loop in unmap(), no functional change

keep in sync with ld.so malloc.c

- An error in the multithreaded case could print the wrong function name
- Start with a full page of struct region_info's
- Save an mprotect in the init code: allocate 3 pages with none and
make the middle page r/w instead of a r/w allocation and two calls to make the
guard pages none

- do not junk pages returned by free_bytes(), all freed chunks are already
junked
- freezero(): only clear requested size

Zap the rotor, it was a wrong idea. Cluebat applied by kshe who
came also up with this diff. Simple, no bias and benchmarks show the extra
random calls disappear in te measurement noise.

Move to ffs(3) for bitmask scanning. I played with this earlier,
but at that time ffs function calls were generated instead of the
compiler inlining the code. Now that ffs is marked protected in
libc this is handled better. Thanks to kshe who prompted me to
look at this again.

optimization and some cleanup; mostly from kshe (except the unmap() part)

Only init chunk_info once, plus some moving of code to group related functions.

step one in avoiding unneccesary init of chunk_info;
some cleanup; tested by sthen@ on a ports build

's' should include 'f'; from Jacqueline Jolicoeur

Restore a return that was inadvertently removed from freezero() in r1.234,
which results in an internal double free when internal functions are not
in use.

ok otto@

do not return f() where f is a void function; loop var type fix

Use dprintf instead of snprintf/write

Make delayed free non-optional and make F do an extensive double free check.
ok tb@ tedu@

mapalign returns MAP_FAILED for failuer; from George Koehler

check double free before canary for chunks; ok millert@

two MALLOC_STATS only tweaks; one from David CARLIER, the other found by clang

one more instance of the previous commit; also initialize ->offset to a
definite value in the size == 0 case

Only access offset if canaries are enabled *and* size > 0, otherwise offset
is not initialized. Problem spotted by Carlin Bingham; ok phessler@ tedu@

port the RBT code to userland by making it part of libc.

src/lib/libc/gen/tree.c is a copy of src/sys/kern/subr_tree.c, but with
annotations for symbol visibility. changes to one should be reflected
in the other.

the malloc debug code that uses RB code is ported to RBT.

because libc provides the RBT code, procmap doesn't have to reach into
the kernel and build subr_tree.c itself now.

mild enthusiasm from many
ok guenther@

- fix bug wrt posix_memalign(3) of blocks between half a page and a page
- document posix_memalign() does not play nice with reacallocarray(3) and
freezero(3)

For small allocations (chunk) freezero only validates the given
size if canaries are enabled. In that case we have the exact requested
size of the allocation. But we can at least check the given size
against the chunk size if C is not enabled. Plus add some braces
so my brain doesn't have to scan for dangling else problems when I
see this code.

don't forget to fill in canary bytes for posix_memalign(3); reported by
and ok jeremy@

whitespace fixes

allow clearing less than allocated and document freezero(3) better

Introducing freezero(3) a version of free that guarantees the process
no longer has access to the content of a memmory object. It does
this by either clearing (if the object memory remains cached) or
by calling munmap(2). ok millert@, deraadt@, guenther@

first print size in meta-data then supplied arg size when an inconsistency is
detected wrt recallocarray()

small cleanup & optimization; ok deraadt@ millert@

add a helper function to print all pools #ifdef MALLOC_STATS
from David CARLIER

move recallocarray to malloc.c and
- use internal meta-data to do more consistency checking (especially with
option C)
- use cheap free if possible
ok deraadt@

Add a NULL test to wrterror() to avoid a NULL deref when called from a
free() error path.

ok otto@

fix a comment and rm some dead code as a result of the previous diff

Let realloc handle and produce moved pointers for allocations between
half a page and a page. ok jmatthew@ tb@

1. When shrinking a chunk allocation, compare the size of the current
allocation to the size of the new allocation (instead of the requested size).
2. Previously realloc takes the easy way and always reallocates if C is
active. This commit fixes by carefully updating the recorded requested
size in all cases, and writing the canary bytes in the proper location
after reallocating.
3. Introduce defines to test if MALLOC_MOVE should be done and to
compute the new value.

MALLOC_STATS tweaks, by default not compiled in

small tweak to also check canaries if F is in effect

remove some old option letters and also make P non-settable. It has
been the default for ages, and I see no valid reason to be able to
disable it. ok natano@

Pages in the malloc cache are either reused quickly or unmapped
quickly. In both cases it does not make sense to set hints on them.
So remove that option, which is just a remainder of old times when
malloc used to hold on to pages. ok stefan@

- fix MALLOC_STATS compile
- redundant cast is redundant

fix some void * arithmetic by casting

and recommit with fixed GC

backout for now; flag combination GC is not ok

Also place canaries in > page sized objects (if C is in effect); ok tb@

Wrap _malloc_init() so internal calls go directly

prodded by otto@
ok kettenis@ otto@

0xd0 -> 0xdb; ok deraadt@ millert@ tedu@

optimize canary code a bit by storing offset of sizes table instead of
recomputing it all the time

stray tab

Beter implementation of chunk canaries: store size in chunk meta data
instead of chunk itself; does not change actual allocated size; ok tedu@

Delete casts to off_t and size_t that are implied by assignments
or prototypes. Ditto for some of the char* and void* casts too.

verified no change to instructions on ILP32 (i386) and LP64 (amd64)
ok natano@ abluhm@ deraadt@ millert@

move page junking tp unmap(), right before we stick the region in the cache;
ok tedu@

Less lock contention by using more pools for mult-threaded programs.
tested by many (thanks!) ok tedu, guenther@

black magic for sparc page size can go

wrterror() is fatal, delete dead code; ok tom@ natano@ tedu@

J/j is a three valued option, document and fix code to actuall support that
with a little help from jmc@ for the man page bits
ok jca@ and a reluctant tedu@

adapt S option: add C, rm F (not relevant with 0 cache and disables
chunk rnd), rm P: is default

Back out previous; otto saw a potential race that could lead to a
double unmap and I experienced a much more unstable firefox.

discussed with otto on icb

defer munmap to after unlocking malloc. this can (unfortunately) be an
expensive syscall, and we don't want to tie up other threads. there's no
need to hold the lock, so defer it to afterwards.
from Michael McConville
ok deraadt

two times a define to an inline function, from Michael McConville; ok djm@

tweak MALLOC_STATS printing (switched off by default), prodded by
Michael McConville

redundant memset(3), from Michael McConville, ok armani@

properly guard to macros

ok otto@

small step towards multiple pools: move two globls into the struct dir_info
ok @stefan armani@

environ and __progname are not declared in a public header; declare them
in libc's hidden/stdlib.h instead of in each .c file that needs one

ok deraadt@ gsoares@ mpi@

refactor option letter parsing into a subfunction, to increase clarity
about which options are turned on/off by 's' and 'S'
ok tedu

Don't crash dumping malloc stats if malloc_init hasn't been called, noted by
David CARLIER

Long ago, malloc internally had two kinds of failures, warnings and errors.
The 'A' option elevated warnings to errors, and has been the default for some
time. Then warnings were effectively eliminated in favor of everything
being an error, but then the 'a' flag turned real errors into warnings!
Remove the 'a' option entirely. You shouldn't have used it anyway.
ok tb tdeval

another case where bad things would happen after wrterror

if somebody makes the mistake of disabling abort, don't deref null in
validate_junk. from Michal Mazurek

Integrate two patches originally from Daniel Micay.
1. Optionally add random "canaries" to the end of an allocation. This
requires increasing the internal size of the allocation slightly, which
probably results in a large effective increase with current power of two
sizing. Therefore, this option is only enabled via 'C'.
2. When writing junk (0xdf) to freed chunks (current default behavior),
check that the junk is still intact when finally freeing the delayed chunk
to catch some potential use after free. This should be pretty cheap so
there's no option to control it separately.
ok deraadt tb

For now, permit overriding of the malloc family, to make emacs happy

Wrap <stdlib.h> so that calls go direct and the symbols not in the
C standard are all weak.
Apply __{BEGIN,END}_HIDDEN_DECLS to gdtoa{,imp}.h, hiding the
arch-specific __strtorx, __ULtox_D2A, __strtorQ, __ULtoQ_D2A symbols.

improve realloc. when expanding a region, actually use the free page cache
instead of simply zapping it. this can save many syscalls in a program
that repeatedly grows and shrinks a buffer, as observed in the wild.

Move to the <limits.h> universe.
review by millert, binary checking process with doug, concept with guenther

rename kern enter/exit macros to malloc enter/leave to better reflect
what's going on.

a small tweak to improve malloc in multithreaded programs. we don't need
to hold the malloc lock across mmap syscalls in all cases. dropping it
allows another thread to access the existing chunk cache if necessary.
could be improved to be a bit more aggressive, but i've been testing this
simple diff for some time now with good results.

reduce obvious dependency on global g_pool by moving to local aliases
ok otto

extra evil spaces snuck in over the last while

Move to a smaller rbytes buffer and skip a random part. Not to
improve the random stream itself (it doesn't), but to introduce
noise in the arc4random calling pattern. Thanks to matthew@ who
pointed out bias in a previous diff, ok deraadt@ matthew@

move random bytes buffer to be part of mmaped pages; ok tedu@

move all stats collecting under MALLOC_STATS; ok krw@

fix MALLOC_STATS (not compiled in by default); ok tedu@

factor out a bit of the chunk index code and use it to make sure that a
freed chunk is actually freeable immediately. catch more errors.
hints/ok otto

change to having four freelists per size, to reduce another source of
deterministic behavior. four selected because it's more than three, less
than five. i.e., no particular reason.

fix MALLOC_STATS code that was broken in rev 1.159, not compiled in by default

move reallocarray() to a seperate file so that -portable applications
can avoid reinventing the wheel
ok guenther schwarze

comment style fix

ok crickets@

nibbles aren't enough random, use bytes. does a better job of picking
a free chunk at random and may allow to increase delayed chunk array.
ok otto

remove Z option and default to something halfway to J.
we always junk small chunks now, and the first part of pages,
but only after free. J still does the old thing. j disables everything.
Consider experimental as we evaluate performance in the real world.
ok otto

explain a bit more what's going on for stupid me.
okay otto@

Better, cleaner hash function that computes the same on be and le archs.
Should improve sparc64 and other be archs. ok matthew@ miod@

change mallocarray to reallocarray. useful in a few more situations.
malloc can, as always, be emulated via realloc(NULL).
ok deraadt

Introducing: void *mallocarray(size_t nmemb, size_t size);
Like calloc(), except without the cleared-memory gaurantee
ok beck guenther, discussed for more than a year...

print pid in error messages; ok reyk@

Update Copyright notice; ok otto@ beck@ deraadt@.
This is merely a by-product of figuring out the amount of phk@ code
contained herein; i'm not planning to hack on this file.

Poul-Henning Kamp informed me he is allright with this licensing change.

avoid arithetic on void *
ok guenther otto

Fix bug in random offset introduced in rev 1.143; random range was
expanded, but not enough due to precedence error. Spotted by Thorsten Glaser.

Add a new malloc option 'U' => "Free unmap" that does the guarding/
unmapping of freed allocations without disabling chunk randomisation
like the "Freeguard" ('F') option does. Make security 'S' option
use 'U' and not 'F'.

Rationale: guarding with no chunk randomisation is great for debugging
use-after-free, but chunk randomisation offers better defence against
"heap feng shui" style attacks that depend on carefully constructing a
particular heap layout so we should leave this enabled when requesting
security options.

Fix precedence bug (& has lower precedence than !=).

Okay otto@.

Found by Michal Mazurek <akfaew at jasminek dot net>, thanks!

use PAGE_SHIFT instead of PGSHIFT, in preperation for future
param.h symbol reduction.
ok guenther

after a talk with ariane, use MAP_FIXED for mquery to avoid the cost of
scanning for free space if the hint isn't available.
also, on further inspection, this will prevent pmap_prefer from "improving"
our hint.

two changes which should improve realloc. first, fix zapcacheregion to
clear out the entire requested area, not just a perfect fit. second,
use mquery to check for room to avoid getting an address we don't like
and having to send it back.

two small fixes to free page cache. first, we need two nibbles of random
in order to span the the entire cache. second, on free use the same offset
to put things in the cache instead of always starting at zero.
ok otto

Support larger-than-page-alignment requests in posix_memalign() by
overallocating and then releasing unneeded memory pages.

ok otto

- Test for the retrieved page address not being NULL. This turns free((void*)1)
into an bogus pointer error instead of a segfault.
- Document that we use the assumption that a non-MAP_FIXED mmap() with
hint 0 never returns NULL.

Make struct chunk_info a variable sized struct, wasting less
space for meta data by only allocating space actually needed for
the bitmap (modulo alignment requirements). ok deraadt@