#BSDBOY

Bugs | Books | Mailing List (marc.info) | Twitter | Github | StackExchange | LinkedIn | About Me

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

debug_with_gdb
Fig.1 malloc debugging with gdb

Hi there,

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

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, OpenBSD malloc(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 of malloc(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".

Followed the below steps to compile the libc with debug symbols


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,

prologue:

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.

epilogue:

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 [code snippet #00], we can see that p is getpool() and fn is the function string, that is, "malloc" and from the [code snippet 01], 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 the [code snippet #02] we 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 the [code snippet #01] it 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 [code snippet #03], 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:

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 [code snippet #04], 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 [code snippet #03], 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:

We are still in function _malloc_init(int from_rthreads), so, as per the [code snippet #03], 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 [code snippet #01], 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 [code snippet #00], 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...

References:

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
Share on Facebook | Share on Twitter | Share on LinkedIn