A Deep dive into OpenBSD malloc(3) internals

Tale of OpenBSD secure memory allocator internals - malloc(3)

Hi there,

It's been a very long time I haven't written anything after my last OpenBSD blogs, that is,

• OpenBSD Kernel Internals — Creation of process from user-space to kernel space .

• OpenBSD: Introduction to `execpromises` in the pledge(2)

• pledge(2): OpenBSD's defensive approach to OS Security

So, again I started reading OpenBSD source codes with debugger after reducing my sleep timings and managing to get some time after professional life. This time I have picked one of my favourite item from my wishlist to learn and share, that is, OpenBSDmalloc(3), secure allocator

I will try to keep it as n part series due to lengthy content and this series will be mostly focussed on user-space code ofmalloc(3) and friends

First of all, I would like to thanks Otto Moerbeek , Bryan Steele and Fabien Romano for helping me to understand the malloc(3) internals and cleared all my queries.

So, we should start now... :)

I have used the following sample code to start my journey with the OpenBSD 6.6-stable malloc(3)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int
main(int argc, char **argv) {
	char *buff1 = NULL;
	buff1 = (char *)malloc(8);
	strcpy(buff1, argv[1]);
	free(buff1);
	return 0;
}

sample code used for learning internals

Compiled the libc with debug symbols and switched off the optimization by compiling it with clang option "-O0 -g".

1. cd $openbsd_src_directory
2. cd lib/libc
3. CFLAGS="-g -O0" CXXFLAGS="-g -O0" make obj
4. CFLAGS="-g -O0" CXXFLAGS="-g -O0" make

I haven't installed it and used gdb-style debugging approach for code reading instead of debugging with printf style debugging.

For printf style debugging, one can use dprintf(3) or write(2) calls to print anything but keep in mind that after installation of libc with printf statements it will dump lots of information for each and every binary, so installation step is no use for malloc(3) debugging.

I would say one can either compile and use LD_PRELOAD to load the compiled libc and use debugger or one can compile with printf statements then use the same LD_PRELOAD for that specific sample code.

So, just after the malloc(3) from the sample code, it directly jumps to function malloc(size_t size) from file /usr/src/lib/libc/stdlib/malloc.c:1278

1277 void *
1278 malloc(size_t size)
1279 {
1280         void *r;
1281         struct dir_info *d;
1282         int saved_errno = errno;
1283
1284         PROLOGUE(getpool(), "malloc")
1285         r = omalloc(d, size, 0, CALLER);
1286         EPILOGUE()
1287         return r;
1288 }

code snippet #00

As explained by the developer Otto@ in the tweet on twitter that struct dir_info contains all the meta information malloc needs to keep track of what page regions have been allocated, which pages regions are in the free-cache and for pages of chunks which chunks are free and which are allocated.

So, as per the code given above, one can see after some basic initialization-declaration, there is some macro PROLOGUE and EPILOGUE. It means the same like how it sounds, usually these two means,

Function prologue . In assembly language programming, the function prologue is a few lines of code at the beginning of a function, which prepare the stack and registers for use within the function. Here, instead of preparing the stack and registers, it initializes some other necessary malloc requirements that we will see later.

Function epilogue reverses the actions of the function prologue and returns control to the calling function.

PROLGOUE macro given below:

1256 #define PROLOGUE(p, fn)                 \
1257         d = (p);                        \
1258         if (d == NULL) {                \
1259                 _malloc_init(0);        \
1260                 d = (p);                \
1261         }                               \
1262         _MALLOC_LOCK(d->mutex);         \
1263         d->func = fn;                   \
1264         if (d->active++) {              \
1265                 malloc_recurse(d);      \
1266                 return NULL;            \
1267         }                               \

code snippet #01

As from the, we can see that p is getpool() and fn is the function string, that is, "malloc" and from the, we can see that it first calls getpool() function and the code for getpool() given below

270 static inline struct dir_info *
271 getpool(void)
272 {
273         if (!mopts.malloc_mt)
274                 return mopts.malloc_pool[1];
275         else    /* first one reserved for special pool */
276                 return mopts.malloc_pool[1 + TIB_GET()->tib_tid %
277                     (mopts.malloc_mutexes - 1)];
278 }

code snippet #02

In thewe can see that first it checks whether it has multi-threads or single-threads. And, in our case it is single threaded binary, so after if it returns mopts.malloc_pool[1] which is NULL .

Now, after that from theit checks whether d is NULL or not. In our case it is NULL as at first it will always be NULL after that it calls _malloc_init(0) but when d is not NULL then it assigns fn to d->func then check and increment the d->active then calls malloc_recurse(d) and returns NULL but for our situation it is not the flow.

Code for _malloc_init(0) given below

1207 void
1208 _malloc_init(int from_rthreads)
1209 {
1210         u_int i, nmutexes;
1211         struct dir_info *d;
1212 
1213         _MALLOC_LOCK(1);
1214         if (!from_rthreads && mopts.malloc_pool[1]) {
1215                 _MALLOC_UNLOCK(1);
1216                 return;
1217         }
1218         if (!mopts.malloc_canary)
1219                 omalloc_init();
1220 
1221         nmutexes = from_rthreads ? mopts.malloc_mutexes : 2;
1222         if (((uintptr_t)&malloc_readonly & MALLOC_PAGEMASK) == 0)
1223                 mprotect(&malloc_readonly, sizeof(malloc_readonly),
1224                     PROT_READ | PROT_WRITE);
1225         for (i = 0; i < nmutexes; i++) {
1226                 if (mopts.malloc_pool[i])
1227                         continue;
1228                 if (i == 0) {
1229                         omalloc_poolinit(&d, MAP_CONCEAL);
1230                         d->malloc_junk = 2;
1231                         d->malloc_cache = 0;
1232                 } else {
1233                         omalloc_poolinit(&d, 0);
1234                         d->malloc_junk = mopts.def_malloc_junk;
1235                         d->malloc_cache = mopts.def_malloc_cache;
1236                 }
1237                 d->mutex = i;
1238                 mopts.malloc_pool[i] = d;
1239         }
1240 
1241         if (from_rthreads)
1242                 mopts.malloc_mt = 1;
1243         else
1244                 mopts.internal_funcs = 1;
1245 
1246         /*
1247          * Options have been set and will never be reset.
1248          * Prevent further tampering with them.
1249          */
1250         if (((uintptr_t)&malloc_readonly & MALLOC_PAGEMASK) == 0)
1251                 mprotect(&malloc_readonly, sizeof(malloc_readonly), PROT_READ);
1252         _MALLOC_UNLOCK(1);
1253 }

code snippet #03

In the, we can see that first it does some MALLOC_LOCKing and checks for the from_rthreads and also for mopts.malloc_pool[1] as an outcome it is not true due to mopts.malloc_pool[1] which is NULL

Then, after that it checks for mopts.malloc_canary and it wil be always 0 first time due to structure initialized to zero (0) and then it calls function omalloc_init() and code for the same given below

405	static void
406	omalloc_init(void)
407	{
408		char *p, *q, b[16];
409		int i, j, mib[2];
410		size_t sb;
411
412		/*
413		 * Default options
414		 */
415		mopts.malloc_mutexes = 8;
416		mopts.def_malloc_junk = 1;
417		mopts.def_malloc_cache = MALLOC_DEFAULT_CACHE;
418
419		for (i = 0; i < 3; i++) {
420			switch (i) {
421			case 0:
422				mib[0] = CTL_VM;
423				mib[1] = VM_MALLOC_CONF;
424				sb = sizeof(b);
425				j = sysctl(mib, 2, b, &sb, NULL, 0);
426				if (j != 0)
427					continue;
428				p = b;
429				break;
430			case 1:
431				if (issetugid() == 0)
432					p = getenv("MALLOC_OPTIONS");
433				else
434					continue;
435				break;
436			case 2:
437				p = malloc_options;
438				break;
439			default:
440				p = NULL;
441			}
442
443			for (; p != NULL && *p != '\0'; p++) {
444				switch (*p) {
445				case 'S':
446					for (q = "CFGJ"; *q != '\0'; q++)
447						omalloc_parseopt(*q);
448					mopts.def_malloc_cache = 0;
449					break;
450				case 's':
451					for (q = "cfgj"; *q != '\0'; q++)
452						omalloc_parseopt(*q);
453					mopts.def_malloc_cache = MALLOC_DEFAULT_CACHE;
454					break;
455				default:
456					omalloc_parseopt(*p);
457					break;
458				}
459			}
460		}
461
462	#ifdef MALLOC_STATS
463		if (mopts.malloc_stats && (atexit(malloc_exit) == -1)) {
464			dprintf(STDERR_FILENO, "malloc() warning: atexit(2) failed."
465			    " Will not be able to dump stats on exit\n");
466		}
467	#endif /* MALLOC_STATS */
468
469		while ((mopts.malloc_canary = arc4random()) == 0)
470			;
471	}

code snippet #04

OpenBSD malloc(3) has lots of feature and they are configurable using systcl(8) , environment variable MALLOC_OPTIONS and compile-time option malloc_options

So, let's suppose one want to use the canary option then one has to set the option using systcl(8), like I have used it from the command: systcl vm.malloc_conf=C

omalloc_init() does the following things:

• Initializes some variables of malloc_readonly structure to default values like mopts.malloc_mutexes is the default number of mutexes, mopts.def_malloc_junk is the default number of junk filling and mopts.def_malloc_cache is the default number of free page cache

• Then, it checks one by one for all 3 ways that is mentioned above for setting a malloc option. In our case, I have used systcl(8) option, so for sysctl it goes to case 0: and get the value to char b[16] and then it assigns to pointer to character variable p then after looping for other two it goes for extracting the value that is there in p

• First it checks for the malloc option S which enables all the security auditing features of OpenBSD malloc(3)

• If it is there then it calls omalloc_parseopt(*q); function then after that it sets mopts.def_malloc_cache to 0 or to MALLOC_DEFAULT_CACHE , depends on whether it is S or s
• If it is not there, then it simply calls the function omalloc_parseopt(*p);

function omalloc_parseopt(char opt) extracts the character and in our case it is C for malloc canary, so after parsing, it goes to case 'C' and sets mopts.chunk_canaries to 1 , it does the same for other characters and sets or enables/initializes their variables. Code for the same function given below:

322	static void
323	omalloc_parseopt(char opt)
324	{
325		switch (opt) {
326		case '+':
327			mopts.malloc_mutexes <<= 1;
328			if (mopts.malloc_mutexes > _MALLOC_MUTEXES)
329				mopts.malloc_mutexes = _MALLOC_MUTEXES;
330			break;
331		case '-':
332			mopts.malloc_mutexes >>= 1;
333			if (mopts.malloc_mutexes < 2)
334				mopts.malloc_mutexes = 2;
335			break;
336		case '>':
337			mopts.def_malloc_cache <<= 1;
338			if (mopts.def_malloc_cache > MALLOC_MAXCACHE)
339				mopts.def_malloc_cache = MALLOC_MAXCACHE;
340			break;
341		case '<':
342			mopts.def_malloc_cache >>= 1;
343			break;
344		case 'c':
345			mopts.chunk_canaries = 0;
346			break;
347		case 'C':
348			mopts.chunk_canaries = 1;
349			break;
350	#ifdef MALLOC_STATS
351		case 'd':
352			mopts.malloc_stats = 0;
353			break;
354		case 'D':
355			mopts.malloc_stats = 1;
356			break;
357	#endif /* MALLOC_STATS */
358		case 'f':
359			mopts.malloc_freecheck = 0;
360			mopts.malloc_freeunmap = 0;
361			break;
362		case 'F':
363			mopts.malloc_freecheck = 1;
364			mopts.malloc_freeunmap = 1;
365			break;
366		case 'g':
367			mopts.malloc_guard = 0;
368			break;
369		case 'G':
370			mopts.malloc_guard = MALLOC_PAGESIZE;
371			break;
372		case 'j':
373			if (mopts.def_malloc_junk > 0)
374				mopts.def_malloc_junk--;
375			break;
376		case 'J':
377			if (mopts.def_malloc_junk < 2)
378				mopts.def_malloc_junk++;
379			break;
380		case 'r':
381			mopts.malloc_realloc = 0;
382			break;
383		case 'R':
384			mopts.malloc_realloc = 1;
385			break;
386		case 'u':
387			mopts.malloc_freeunmap = 0;
388			break;
389		case 'U':
390			mopts.malloc_freeunmap = 1;
391			break;
392		case 'x':
393			mopts.malloc_xmalloc = 0;
394			break;
395		case 'X':
396			mopts.malloc_xmalloc = 1;
397			break;
398		default:
399			dprintf(STDERR_FILENO, "malloc() warning: "
400	                    "unknown char in MALLOC_OPTIONS\n");
401			break;
402		}
403	}

code snippet #05

There are some ifdef MALLOC_STATS in the entire source, which means it dumps extra malloc stats information whenever requires. So, as from the, after completing omalloc_parseopt(char opt) , there is some MALLOC_STATS condition then after them, a random cookie assigns to mopts.malloc_canary using arc4random()

After the completion of omalloc_init() , coming again to, there is a variable named nmutexes which sets bydefault to 2 for single-threaded programs, we have already seen the initalization of mopts.malloc_mutexes default to 8 for multi-threaded programs in the function omalloc_init() . Here, for single-threaded, the value of variable from_rthread is 0

Then, it checks for MALLOC_PAGEMASK bit for malloc_readonly address or simply we can say that it is checking the last 12 bits of the malloc_readonly structure address and all 12 bits must be 0 to apply perm bit PROT_READ and PROT_WRITE . I would also say it is also checking for even address

After that, there is a loop till the nmutexes which is 2 for our case, single-threaded. For single-threaded programs, it maintains two malloc dir_info pools as indicates from the variable nmutexes . One for MAP_CONCEALED memory (#0) and one for regular (#1). For multi-threaded porgram more pools are created. This is to avoid contention, accesses to diffrent pools can run concurently [ref. [1] related to multi-pools - mailing list [2] github diff for more pools ]

omalloc_poolinit(&d, MAP_CONCEAL); when if i == 0 for MAP_CONCEALED memory and else , omalloc_poolinit(&d, 0); for regular memory pools.

omalloc_poolinit()code given below:

473 static void
474 omalloc_poolinit(struct dir_info **dp, int mmap_flag)
475 {
476         char *p;
477         size_t d_avail, regioninfo_size;
478         struct dir_info *d;
479         int i, j;
480
481         /*
482          * Allocate dir_info with a guard page on either side. Also
483          * randomise offset inside the page at which the dir_info
484          * lies (subject to alignment by 1 << MALLOC_MINSHIFT)
485          */
486         if ((p = MMAPNONE(DIR_INFO_RSZ + (MALLOC_PAGESIZE * 2), mmap_flag)) ==
487             MAP_FAILED)
488                 wrterror(NULL, "malloc init mmap failed");
489         mprotect(p + MALLOC_PAGESIZE, DIR_INFO_RSZ, PROT_READ | PROT_WRITE);
490         d_avail = (DIR_INFO_RSZ - sizeof(*d)) >> MALLOC_MINSHIFT;
491         d = (struct dir_info *)(p + MALLOC_PAGESIZE +
492             (arc4random_uniform(d_avail) << MALLOC_MINSHIFT));
493
494         rbytes_init(d);
495         d->regions_free = d->regions_total = MALLOC_INITIAL_REGIONS;
496         regioninfo_size = d->regions_total * sizeof(struct region_info);
497         d->r = MMAP(regioninfo_size, mmap_flag);
498         if (d->r == MAP_FAILED) {
499                 d->regions_total = 0;
500                 wrterror(NULL, "malloc init mmap failed");
501         }
502         for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
503                 LIST_INIT(&d->chunk_info_list[i]);
504                 for (j = 0; j < MALLOC_CHUNK_LISTS; j++)
505                         LIST_INIT(&d->chunk_dir[i][j]);
506         }
507         STATS_ADD(d->malloc_used, regioninfo_size + 3 * MALLOC_PAGESIZE);
508         d->mmap_flag = mmap_flag;
509         d->malloc_junk = mopts.def_malloc_junk;
510         d->malloc_cache = mopts.def_malloc_cache;
511         d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d;
512         d->canary2 = ~d->canary1;
513
514         *dp = d;
515 }

code snippet #06

omalloc_poolinit(struct dir_inf **dp, int mmap_flag) does the following things:

96 #define MMAPNONE(sz,f)  mmap(NULL, (sz), PROT_NONE, \
97     MAP_ANON | MAP_PRIVATE | (f), -1, 0)

The mmap() function causes the contents of fd, starting at offset, to be
     mapped in memory at the given addr.  The mapping will extend at least len
     bytes, subject to page alignment restrictions.

     The addr argument describes the address where the system should place the
     mapping.  If the MAP_FIXED flag is specified, the allocation will happen
     at the specified address, replacing any previously established mappings
     in its range.  Otherwise, the mapping will be placed at the available
     spot at addr; failing that it will be placed "close by".  If addr is NULL
     the system can pick any address.  Except for MAP_FIXED mappings, the
     system will never replace existing mappings.

     The len argument describes the minimum amount of bytes the mapping will
     span.  Since mmap() maps pages into memory, len may be rounded up to hit
     a page boundary.  If len is 0, the mapping will fail with EINVAL.

sz = DIR_INFO_RSZ + (MALLOC_PAGESIZE * 2)
where DIR_INFO_RSZ = ((sizeof(struct dir_info) + MALLOC_PAGEMASK) & ~MALLOC_PAGEMASK)
MALLOC_PAGEMASK = 4095 bytes
MALLOC_PAGESIZE = 4096 bytes
So, DIR_INFO_RSZ becomes (4284 + 4095) & ~4095 = 8192 bytes
and sz becomes 8192 + (4096 * 2) = 16384 bytes
and, f = MMAP_CONCEAL; which means it prevents from leaking the information and also it excludes the mapping from core dumps

d_avail = (8192 - 4824) >> 4 = 3368 >> 4 = 210

d = (struct dir_info *)(p + MALLOC_PAGESIZE + (arc4random_uniform(d_avail) << MALLOC_MINSHIFT));

303 static void
304 rbytes_init(struct dir_info *d)
305 {
306         arc4random_buf(d->rbytes, sizeof(d->rbytes));
307         /* add 1 to account for using d->rbytes[0] */
308         d->rbytesused = 1 + d->rbytes[0] % (sizeof(d->rbytes) / 2);
309 }

105 struct region_info {
106         void *p;                /* page; low bits used to mark chunks */
107         uintptr_t size;         /* size for pages, or chunk_info pointer */
108 #ifdef MALLOC_STATS
109         void *f;                /* where allocated from */
110 #endif
111 };

...
...
...
502         for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
503                 LIST_INIT(&d->chunk_info_list[i]);
504                 for (j = 0; j < MALLOC_CHUNK_LISTS; j++)
505                         LIST_INIT(&d->chunk_dir[i][j]);
506         }
...
...
...

chunk_info_list[0]
	chunk_dir[0][0]
	chunk_dir[0][1]
	chunk_dir[0][2]
	chunk_dir[0][3]
...
...
...
chunk_info_list[11]
	chunk_dir[11][0]
	chunk_dir[11][1]
	chunk_dir[11][2]
	chunk_dir[11][3]

...
...
...

...
...
...
508         d->mmap_flag = mmap_flag;
509         d->malloc_junk = mopts.def_malloc_junk;
510         d->malloc_cache = mopts.def_malloc_cache;
511         d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d;
512         d->canary2 = ~d->canary1;
513
514         *dp = d;
515 }
	/* where it is already mentioned above code snippets that mopts.def_malloc_junk is 1 and
	 *  mopts.def_malloc_cache is 64, already initialized default values in omalloc_init() 
	 */

We are still in function _malloc_init(int from_rthreads) , so, as per the, for i == 0 , we have completed the function omalloc_poolinit(&d, MAP_CONCEAL); , now after that, it assigns d->malloc_junk = 2; and d->malloc_cache = 0;

Then, it saves the index i to d->mutex and stored the initialized MAP_CONCEALED pool to mopts.malloc_pool[i] = d;

The value of nmutexes is 2, so, now loop will again do the whole same operations for index i == 1 or we can say for i != 0 .So, this time also it invokes omalloc_poolinit(&d, 0) but with no flag, remember, last time it was MAP_CONCEAL, this time, it is 0 . So, omalloc_poolinit(&d, 0) performs the same operations but only the diff is with no flag value or with flag value 0

After completion of function omalloc_poolinit(&d, 0) , it sets junk value to default junk value and same for malloc_cache, that is, d->malloc_junk = mopts.def_malloc_junk; and d->malloc_cache = mopts.def_malloc_cache; . Now, again for i = 1 it does the same thing, that is, saving the new index 1 to d->mutex and stores the pool to mopts.malloc_pool[i] = d

So, now mopts.malloc_pool has two pools, mopts.malloc_pool[0] and mopts.malloc_pool[1]

Next, it checks for multi-threading from variable from_rthreads , if the value is non-zero then it sets mopts.malloc_mt = 1 which shows that program is multi-threaded but for our case it is zero (0), so, it doesn't go in that code flow and then the else code flow executes and sets mopts.internal_funcs = 1 , from the structure malloc_readonly , it shows that setting internal_funcs means to use better function like recallocarray/freezero but I haven't seen them for our case, maybe they have used it for some other scenarios like in case of calloc, etc. recallocarray(3) - mailing list

Finally it sets the perms to readonly, to prevent further tampering with them, again it checks last 12 bits and if they are 0 then it sets perms to PROT_READ, and _malloc_init(0) completed

Now, we go back to the PROGLOGUE macro code in the, I have pasted the code again:

1256 #define PROLOGUE(p, fn)                 \
1257         d = (p);                        \
1258         if (d == NULL) {                \
1259                 _malloc_init(0);        \
1260                 d = (p);                \
1261         }                               \
1262         _MALLOC_LOCK(d->mutex);         \
1263         d->func = fn;                   \
1264         if (d->active++) {              \
1265                 malloc_recurse(d);      \
1266                 return NULL;            \
1267         }                               \

revisited PROLOGUE macro code

So, as from the PROLOGUE code, we can see that we have completed the malloc_init(0) .Now, if we remember correctly, here p refers to the function getpool() , calls getpool() function again and this time also due to single-threaded program, it returns mopts.malloc_pool[1] , which has the regular pool, not MAP_CONCEALED one, return the same to d then malloc_lock and assigns fn to d->fn , here fn means func string "malloc". It checks and incremented the d->active and doesn't go inside the if code-flow due to 0 value of d->active

As one can see from the, I have pasted it again below

1277 void *
1278 malloc(size_t size)
1279 {
1280         void *r;
1281         struct dir_info *d;
1282         int saved_errno = errno;
1283
1284         PROLOGUE(getpool(), "malloc")
1285         r = omalloc(d, size, 0, CALLER);
1286         EPILOGUE()
1287         return r;
1288 }

revisited malloc code

From line no. 1285, we can see that after PROLOGUE it calls omalloc(d, size, CALLER) . Code for omalloc(d, size, CALLER) given below:

1126	static void *
1127	omalloc(struct dir_info *pool, size_t sz, int zero_fill, void *f)
1128	{
1129		void *p;
1130		size_t psz;
1131
1132		if (sz > MALLOC_MAXCHUNK) {
1133			if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) {
1134				errno = ENOMEM;
1135				return NULL;
1136			}
1137			sz += mopts.malloc_guard;
1138			psz = PAGEROUND(sz);
1139			p = map(pool, NULL, psz, zero_fill);
1140			if (p == MAP_FAILED) {
1141				errno = ENOMEM;
1142				return NULL;
1143			}
1144			if (insert(pool, p, sz, f)) {
1145				unmap(pool, p, psz, 0, 0);
1146				errno = ENOMEM;
1147				return NULL;
1148			}
1149			if (mopts.malloc_guard) {
1150				if (mprotect((char *)p + psz - mopts.malloc_guard,
1151				    mopts.malloc_guard, PROT_NONE))
1152					wrterror(pool, "mprotect");
1153				STATS_ADD(pool->malloc_guarded, mopts.malloc_guard);
1154			}
1155
1156			if (MALLOC_MOVE_COND(sz)) {
1157				/* fill whole allocation */
1158				if (pool->malloc_junk == 2)
1159					memset(p, SOME_JUNK, psz - mopts.malloc_guard);
1160				/* shift towards the end */
1161				p = MALLOC_MOVE(p, sz);
1162				/* fill zeros if needed and overwritten above */
1163				if (zero_fill && pool->malloc_junk == 2)
1164					memset(p, 0, sz - mopts.malloc_guard);
1165			} else {
1166				if (pool->malloc_junk == 2) {
1167					if (zero_fill)
1168						memset((char *)p + sz - mopts.malloc_guard,
1169						    SOME_JUNK, psz - sz);
1170					else
1171						memset(p, SOME_JUNK,
1172						    psz - mopts.malloc_guard);
1173				} else if (mopts.chunk_canaries)
1174					fill_canary(p, sz - mopts.malloc_guard,
1175					    psz - mopts.malloc_guard);
1176			}
1177
1178		} else {
1179			/* takes care of SOME_JUNK */
1180			p = malloc_bytes(pool, sz, f);
1181			if (zero_fill && p != NULL && sz > 0)
1182				memset(p, 0, sz);
1183		}
1184
1185		return p;
1186	}

code snippet #08

omalloc(struct dir_info *pool, size_t sz, int zero_fill, void *f); does the following things...

70 /*
71  * We move allocations between half a page and a whole page towards the end,
72  * subject to alignment constraints. This is the extra headroom we allow.
73  * Set to zero to be the most strict.
74  */
75 #define MALLOC_LEEWAY           0
76 #define MALLOC_MOVE_COND(sz)    ((sz) - mopts.malloc_guard <            \
77                                     MALLOC_PAGESIZE - MALLOC_LEEWAY)
78 #define MALLOC_MOVE(p, sz)      (((char *)(p)) +                        \
79                                     ((MALLOC_PAGESIZE - MALLOC_LEEWAY - \
80                                     ((sz) - mopts.malloc_guard)) &      \
81                                     ~(MALLOC_MINSIZE - 1)))

...
		...
		...
1166				if (pool->malloc_junk == 2) {
1167					if (zero_fill)
1168						memset((char *)p + sz - mopts.malloc_guard,
1169						    SOME_JUNK, psz - sz);
1170					else
1171						memset(p, SOME_JUNK,
1172						    psz - mopts.malloc_guard);

948	/*
949	 * Allocate a chunk
950	 */
951	static void *
952	malloc_bytes(struct dir_info *d, size_t size, void *f)
953	{
954		u_int i, r;
955		int j, listnum;
956		size_t k;
957		u_short	*lp;
958		struct chunk_info *bp;
959		void *p;
960	
961		if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
962		    d->canary1 != ~d->canary2)
963			wrterror(d, "internal struct corrupt");
964	
965		j = find_chunksize(size);
966	
967		r = ((u_int)getrbyte(d) << 8) | getrbyte(d);
968		listnum = r % MALLOC_CHUNK_LISTS;
969		/* If it's empty, make a page more of that size chunks */
970		if ((bp = LIST_FIRST(&d->chunk_dir[j][listnum])) == NULL) {
971			bp = omalloc_make_chunks(d, j, listnum);
972			if (bp == NULL)
973				return NULL;
974		}
975	
976		if (bp->canary != (u_short)d->canary1)
977			wrterror(d, "chunk info corrupted");
978	
979		i = (r / MALLOC_CHUNK_LISTS) & (bp->total - 1);
980	
981		/* start somewhere in a short */
982		lp = &bp->bits[i / MALLOC_BITS];
983		if (*lp) {
984			j = i % MALLOC_BITS;
985			k = ffs(*lp >> j);
986			if (k != 0) {
987				k += j - 1;
988				goto found;
989			}
990		}
991		/* no bit halfway, go to next full short */
992		i /= MALLOC_BITS;
993		for (;;) {
994			if (++i >= bp->total / MALLOC_BITS)
995				i = 0;
996			lp = &bp->bits[i];
997			if (*lp) {
998				k = ffs(*lp) - 1;
999				break;
1000			}
1001		}
1002	found:
1003	#ifdef MALLOC_STATS
1004		if (i == 0 && k == 0) {
1005			struct region_info *r = find(d, bp->page);
1006			r->f = f;
1007		}
1008	#endif
1009	
1010		*lp ^= 1 << k;
1011	
1012		/* If there are no more free, remove from free-list */
1013		if (--bp->free == 0)
1014			LIST_REMOVE(bp, entries);
1015	
1016		/* Adjust to the real offset of that chunk */
1017		k += (lp - bp->bits) * MALLOC_BITS;
1018	
1019		if (mopts.chunk_canaries && size > 0)
1020			bp->bits[bp->offset + k] = size;
1021	
1022		k <<= bp->shift;
1023	
1024		p = (char *)bp->page + k;
1025		if (bp->size > 0) {
1026			if (d->malloc_junk == 2)
1027				memset(p, SOME_JUNK, bp->size);
1028			else if (mopts.chunk_canaries)
1029				fill_canary(p, size, bp->size);
1030		}
1031		return p;
1032	}

919 static int
 920 find_chunksize(size_t size)
 921 {
 922         int r;
 923
 924         /* malloc(0) is special */
 925         if (size == 0)
 926                 return 0;
 927
 928         if (size < MALLOC_MINSIZE)
 929                 size = MALLOC_MINSIZE;
 930         size--;
 931
 932         r = MALLOC_MINSHIFT;
 933         while (size >> r)
 934                 r++;
 935         return r;
 936 }

311 static inline u_char
 312 getrbyte(struct dir_info *d)
 313 {
 314         u_char x;
 315 
 316         if (d->rbytesused >= sizeof(d->rbytes))
 317                 rbytes_init(d);
 318         x = d->rbytes[d->rbytesused++];
 319         return x;
 320 }

get-random-byte then left shits by 8 then OR'ed with again some random byte
		let's suppose,
		1) a =  get-random-bytes
		2) left shift a by 8 
		3) b = get-random-bytes
		4) r = a | b
		for example, 0xd4 -> 0xd400 -> 0xd4cb, so r = 0xd4cb

885 /*
 886  * Allocate a page of chunks
 887  */
 888 static struct chunk_info *
 889 omalloc_make_chunks(struct dir_info *d, int bits, int listnum)
 890 {
 891         struct chunk_info *bp;
 892         void *pp;
 893
 894         /* Allocate a new bucket */
 895         pp = map(d, NULL, MALLOC_PAGESIZE, 0);
 896         if (pp == MAP_FAILED)
 897                 return NULL;
 898
 899         /* memory protect the page allocated in the malloc(0) case */
 900         if (bits == 0 && mprotect(pp, MALLOC_PAGESIZE, PROT_NONE) == -1)
 901                 goto err;
 902
 903         bp = alloc_chunk_info(d, bits);
 904         if (bp == NULL)
 905                 goto err;
 906         bp->page = pp;
 907
 908         if (insert(d, (void *)((uintptr_t)pp | (bits + 1)), (uintptr_t)bp,
 909             NULL))
 910                 goto err;
 911         LIST_INSERT_HEAD(&d->chunk_dir[bits][listnum], bp, entries);
 912         return bp;
 913
 914 err:
 915         unmap(d, pp, MALLOC_PAGESIZE, 0, d->malloc_junk);
 916         return NULL;
 917 }

751 static void *
752 map(struct dir_info *d, void *hint, size_t sz, int zero_fill)
753 {
754	size_t psz = sz >> MALLOC_PAGESHIFT;
755	struct region_info *r, *big = NULL;
756	u_int i;
757	void *p;
758 
759	if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
760	    d->canary1 != ~d->canary2)
761		wrterror(d, "internal struct corrupt");
762	if (sz != PAGEROUND(sz))
763		wrterror(d, "map round");
764 
765	if (hint == NULL && psz > d->free_regions_size) {
766		_MALLOC_LEAVE(d);
767		p = MMAP(sz, d->mmap_flag);
768		_MALLOC_ENTER(d);
769		if (p != MAP_FAILED)
770			STATS_ADD(d->malloc_used, sz);
771		/* zero fill not needed */
772		return p;
773	}
774	for (i = 0; i < d->malloc_cache; i++) {
775		r = &d->free_regions[(i + d->rotor) & (d->malloc_cache - 1)];
776		if (r->p != NULL) {
777			if (hint != NULL && r->p != hint)
778				continue;
779			if (r->size == psz) {
780				p = r->p;
781				r->p = NULL;
782				d->free_regions_size -= psz;
783				if (mopts.malloc_freeunmap)
784					mprotect(p, sz, PROT_READ | PROT_WRITE);
785				if (zero_fill)
786					memset(p, 0, sz);
787				else if (d->malloc_junk == 2 &&
788				    mopts.malloc_freeunmap)
789					memset(p, SOME_FREEJUNK, sz);
790				d->rotor += i + 1;
791				return p;
792			} else if (r->size > psz)
793				big = r;
794		}
795	}
796	if (big != NULL) {
797		r = big;
798		p = r->p;
799		r->p = (char *)r->p + (psz << MALLOC_PAGESHIFT);
800		if (mopts.malloc_freeunmap)
801			mprotect(p, sz, PROT_READ | PROT_WRITE);
802		r->size -= psz;
803		d->free_regions_size -= psz;
804		if (zero_fill)
805			memset(p, 0, sz);
806		else if (d->malloc_junk == 2 && mopts.malloc_freeunmap)
807			memset(p, SOME_FREEJUNK, sz);
808		return p;
809	}
810	if (hint != NULL)
811		return MAP_FAILED;
812	if (d->free_regions_size > d->malloc_cache)
813		wrterror(d, "malloc cache");
814	_MALLOC_LEAVE(d);
815	p = MMAP(sz, d->mmap_flag);
816	_MALLOC_ENTER(d);
817	if (p != MAP_FAILED)
818		STATS_ADD(d->malloc_used, sz);
819	/* zero fill not needed */
820	return p;
821 }

calls map(d, NULL, MALLOC_PAGESIZE, 0);
		After corelating the map() calling from <a href="#code_snippet_12">[code snippet #12]</a> and <a href="#code_map">map() function defination</a>, 
		→ first parameter, d belongs to struct dir_info *d
		→ second parameter, NULL belongs to *hint
		→ third parameter, MALLOC_PAGESIZE belongs to sz
		→ fourth parameter, 0 indicates zero_filling requirements

847 static struct chunk_info *
 848 alloc_chunk_info(struct dir_info *d, int bits)
 849 {
 850         struct chunk_info *p;
 851
 852         if (LIST_EMPTY(&d->chunk_info_list[bits])) {
 853                 size_t size, count, i;
 854                 char *q;
 855
 856                 if (bits == 0)
 857                         count = MALLOC_PAGESIZE / MALLOC_MINSIZE;
 858                 else
 859                         count = MALLOC_PAGESIZE >> bits;
 860
 861                 size = howmany(count, MALLOC_BITS);
 862                 size = sizeof(struct chunk_info) + (size - 1) * sizeof(u_short);
 863                 if (mopts.chunk_canaries)
 864                         size += count * sizeof(u_short);
 865                 size = _ALIGN(size);
 866
 867                 q = MMAP(MALLOC_PAGESIZE, d->mmap_flag);
 868                 if (q == MAP_FAILED)
 869                         return NULL;
 870                 STATS_ADD(d->malloc_used, MALLOC_PAGESIZE);
 871                 count = MALLOC_PAGESIZE / size;
 872
 873                 for (i = 0; i < count; i++, q += size) {
 874                         p = (struct chunk_info *)q;
 875                         LIST_INSERT_HEAD(&d->chunk_info_list[bits], p, entries);
 876                 }
 877         }
 878         p = LIST_FIRST(&d->chunk_info_list[bits]);
 879         LIST_REMOVE(p, entries);
 880         if (p->shift == 0)
 881                 init_chunk_info(d, p, bits);
 882         return p;
 883 }

823 static void
 824 init_chunk_info(struct dir_info *d, struct chunk_info *p, int bits)
 825 {
 826         int i;
 827
 828         if (bits == 0) {
 829                 p->shift = MALLOC_MINSHIFT;
 830                 p->total = p->free = MALLOC_PAGESIZE >> p->shift;
 831                 p->size = 0;
 832                 p->offset = 0xdead;
 833         } else {
 834                 p->shift = bits;
 835                 p->total = p->free = MALLOC_PAGESIZE >> p->shift;
 836                 p->size = 1U << bits;
 837                 p->offset = howmany(p->total, MALLOC_BITS);
 838         }
 839         p->canary = (u_short)d->canary1;
 840
 841         /* set all valid bits in the bitmap */
 842         i = p->total - 1;
 843         memset(p->bits, 0xff, sizeof(p->bits[0]) * (i / MALLOC_BITS));
 844         p->bits[i / MALLOC_BITS] = (2U << (i % MALLOC_BITS)) - 1;
 845 }

p->bits[255 / 16] = (2U << ( 255 % 16)) - 1
		then, p->bits[15] = (2U << ( 15 )) - 1
		then, p->bits[15] = 65536 - 1
		then, p->bits[15] = 65535

564 /*
565  * The hashtable uses the assumption that p is never NULL. This holds since
566  * non-MAP_FIXED mappings with hint 0 start at BRKSIZ.
567  */
568 static int
569 insert(struct dir_info *d, void *p, size_t sz, void *f)
570 {
571         size_t index;
572         size_t mask;
573         void *q;
574
575         if (d->regions_free * 4 < d->regions_total) {
576                 if (omalloc_grow(d))
577                         return 1;
578         }
579         mask = d->regions_total - 1;
580         index = hash(p) & mask;
581         q = d->r[index].p;
582         STATS_INC(d->inserts);
583         while (q != NULL) {
584                 index = (index - 1) & mask;
585                 q = d->r[index].p;
586                 STATS_INC(d->insert_collisions);
587         }
588         d->r[index].p = p;
589         d->r[index].size = sz;
590 #ifdef MALLOC_STATS
591         d->r[index].f = f;
592 #endif
593         d->regions_free--;
594         return 0;
595 }

254 static inline size_t
 255 hash(void *p)
 256 {
 257         size_t sum;
 258         uintptr_t u;
 259
 260         u = (uintptr_t)p >> MALLOC_PAGESHIFT;
 261         sum = u;
 262         sum = (sum << 7) - sum + (u >> 16);
 263 #ifdef __LP64__
 264         sum = (sum << 7) - sum + (u >> 32);
 265         sum = (sum << 7) - sum + (u >> 48);
 266 #endif
 267         return sum;
 268 }

struct pginfo {
    struct pginfo       *next;  /* next on the free list */
    void                *page;  /* Pointer to the page */
    u_short             size;   /* size of this page's chunks */
    u_short             shift;  /* How far to shift for this size chunks */
    u_short             free;   /* How many free chunks */
    u_short             total;  /* How many chunk */
    u_int               bits[1]; /* Which chunks are free */
};

The next field is a pointer to the next structure in the list, or 0 if the
element is the last of the list.

The page field points to the beginning of the page (it is always a multiple of
malloc_pagesize).

The size field is set to the size in bytes of the chunks contained in this page.

The free field is the number of free chunks in the page.

The total field is the sum of the number of free chunks in the page and of the
number of allocated chunks in the page. The page is freed (ie. returned to the
lower layer) whenever ( free == total ) becomes true.

<b>At last, the bits field is a variable size array indicating which chunks in the
page are free chunks. Each chunk is associated with a unique bit in the field,
namely the bit obtained when applying the ( 1 << n ) mask to bits[i] where:

  ( i * MALLOC_BITS ) + n = ( chunk_address & malloc_pagemask ) / chunk_size

MALLOC_BITS is the number of bits a u_int has on the specific architecture phk
malloc is running on. It is defined as follows:

#define MALLOC_BITS     ((int)(8*sizeof(u_int)))

This bit is set to one when the chunk is free, and to 0 when the chunk is in
use. Of course, the effective size of the bits field will depend on the number
of chunks in the page.</b>

...
...
...
981		/* start somewhere in a short */
982		lp = &bp->bits[i / MALLOC_BITS];
983		if (*lp) {
984			j = i % MALLOC_BITS;
985			k = ffs(*lp >> j);
986			if (k != 0) {
987				k += j - 1;
988				goto found;
989			}
990		}
991		/* no bit halfway, go to next full short */
992		i /= MALLOC_BITS;
993		for (;;) {
994			if (++i >= bp->total / MALLOC_BITS)
995				i = 0;
996			lp = &bp->bits[i];
997			if (*lp) {
998				k = ffs(*lp) - 1;
999				break;
1000			}
1001		}
1002	found:
1003	#ifdef MALLOC_STATS
1004		if (i == 0 && k == 0) {
1005			struct region_info *r = find(d, bp->page);
1006			r->f = f;
1007		}
1008	#endif
1009	
1010		*lp ^= 1 << k;
1011	
1012		/* If there are no more free, remove from free-list */
1013		if (--bp->free == 0)
1014			LIST_REMOVE(bp, entries);
1015	
1016		/* Adjust to the real offset of that chunk */
1017		k += (lp - bp->bits) * MALLOC_BITS;
1018	
1019		if (mopts.chunk_canaries && size > 0)
1020			bp->bits[bp->offset + k] = size;
1021	
1022		k <<= bp->shift;
1023	
1024		p = (char *)bp->page + k;
1025		if (bp->size > 0) {
1026			if (d->malloc_junk == 2)
1027				memset(p, SOME_JUNK, bp->size);
1028			else if (mopts.chunk_canaries)
1029				fill_canary(p, size, bp->size);
1030		}
1031		return p;
1032	}

1 /* ffs -- Find the first bit set in the parameter
 2
 3 @deftypefn Supplemental int ffs (int @var{valu})
 4
 5 Find the first (least significant) bit set in @var{valu}.  Bits are
 6 numbered from right to left, starting with bit 1 (corresponding to the
 7 value 1).  If @var{valu} is zero, zero is returned.
 8
 9 @end deftypefn
10
11 */
12
13 int
14 ffs (register int valu)
15 {
16   register int bit;
17
18   if (valu == 0)
19     return 0;
20
21   for (bit = 1; !(valu & 1); bit++)
22         valu >>= 1;
23
24   return bit;
25 }

1. bp->page or pp is the page of chunks and bp is the associated meta-info
		2. k is the chunk number, before shiting, which means k is the index for the chunk in the page bp->page
		3. After shifting, k becomes the byte offset of the chunk inside the bp->page page

938 static void
939 fill_canary(char *ptr, size_t sz, size_t allocated)
940 {
941         size_t check_sz = allocated - sz;
942
943         if (check_sz > CHUNK_CHECK_LENGTH)
944                 check_sz = CHUNK_CHECK_LENGTH;
945         memset(ptr + sz, SOME_JUNK, check_sz);
946 }

1269 #define EPILOGUE()                              \
1270         d->active--;                            \
1271         _MALLOC_UNLOCK(d->mutex);               \
1272         if (r == NULL && mopts.malloc_xmalloc)  \
1273                 wrterror(d, "out of memory");   \
1274         if (r != NULL)                          \
1275                 errno = saved_errno;            \

openbsd# LD_PRELOAD=/usr/src/lib/libc/obj/libc.so.95.1 gdb -q sample
(gdb) br main
Breakpoint 1 at 0x1363: file sample.c, line 7.
(gdb) r AAAABBBBCCCCDDDD
Starting program: /root/test/sample AAAABBBBCCCCDDDD
Breakpoint 1 at 0x4517aff7363: file sample.c, line 7.
Error while reading shared library symbols:
Dwarf Error: wrong version in compilation unit header (is 4, should be 2) [in module /usr/libexec/ld.so]

Breakpoint 1, main (argc=2, argv=0x7f7ffffee678) at sample.c:7
7		char *buff1 = NULL;
Current language:  auto; currently minimal
(gdb) n
8		buff1 = (char *)malloc(8);
(gdb) n
9		strcpy(buff1, argv[1]);
(gdb) x/16x buff1
0x453ec9b6fe0:	0x00000000	0x00000000	0xdbdbdbdb	0xdbdbdbdb
0x453ec9b6ff0:	0x00000000	0x00000000	0x00000000	0x00000000
0x453ec9b7000:	Cannot access memory at address 0x453ec9b7000
(gdb) n
10		free(buff1);
(gdb) x/16x buff1
0x453ec9b6fe0:	0x41414141	0x42424242	0x43434343	0x44444444
0x453ec9b6ff0:	0x00000000	0x00000000	0x00000000	0x00000000
0x453ec9b7000:	Cannot access memory at address 0x453ec9b7000
(gdb) c
Continuing.
sample(3165) in free(): chunk canary corrupted 0x453ec9b6fe0 0x8@0x8

Program received signal SIGABRT, Aborted.
thrkill () at -:3
3	-: No such file or directory.
	in -
Current language:  auto; currently asm
(gdb)

References:

• malloc(3) man page

• OpenBSD community - mailing list

• A new malloc(3) for OpenBSD slides by Otto Moerbeek

• BSD Heap Smashing , paper by bbp@krukh.net on phkmalloc [from security point of view]

• GitHub code history for old commit messages

• information on all the commits in mailing list

• phkmalloc , paper by Poul-Henning Kamp

• malloc(3) code series by Adam Wolk and @DuClare

• Discussions on twitter with developers

• Google :)

I have covered all stuff that I have learned while reading the code of malloc(3). In case, if I have forgotten or missed something, please feel free to update me.

If I have explained something wrongly or incorrectly then please feel free to update or correct me, I am also a learner and beginner so that may happen. :)

Again, a huge thanks to all OpenBSD community and especially Otto@ for helping to understand the malloc internals and patiently listening my all queries :). I am still learning and having dicussions on u_short bit[1] variable for bitmap understanding.

Next, I will share about free(3) internals, its ability to detect the memory corruption bugs and also a bit more about bitmap understanding.

Any doubts/questions, feel free to drop mail @bsdb0y or tweet @twitter

Happy Kernel Hacking