Igor’s tip of the week #57: Shifted pointers 2 – Hex Rays

This week we’ll cover another situation where shifted pointers can be useful.

Intrusive linked lists

This approach is used in many linked list implementations. Let’s consider the one used in the Linux kernel. list.h defines the linked list structure:

struct list_head { 
  struct list_head *next, *prev; 
  };

As an example of its use, consider the struct module from module.h:

struct module {
	enum module_state state;

	/* Member of list of modules */
	struct list_head list;

	/* Unique handle for this module */
	char name[MODULE_NAME_LEN];
	
[..skipped..]
} ____cacheline_aligned __randomize_layout;

Where struct list_head list;is used to link the instances of struct moduletogether. Because the next and prev pointers do not point to the start of struct module, some pointer math is required to access its fields. For this, various macros in list.h are used:

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

/**
 * list_first_entry - get the first element from a list
 * @ptr:	the list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 *
 * Note, that list is expected to be not empty.
 */
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)
/**
 * list_last_entry - get the last element from a list
 * @ptr:	the list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 *
 * Note, that list is expected to be not empty.
 */
#define list_last_entry(ptr, type, member) \
	list_entry((ptr)->prev, type, member)

Let’s look at some functions from module.c. For example, m_show():

static int m_show(struct seq_file *m, void *p)
{
	struct module *mod = list_entry(p, struct module, list);
	char buf[MODULE_FLAGS_BUF_SIZE];
	void *value;

	/* We always ignore unformed modules. */
	if (mod->state == MODULE_STATE_UNFORMED)
		return 0;

	seq_printf(m, "%s %u",
		   mod->name, mod->init_layout.size + mod->core_layout.size);
	print_unload_info(m, mod);

	/* Informative for users. */
	seq_printf(m, " %s",
		   mod->state == MODULE_STATE_GOING ? "Unloading" :
		   mod->state == MODULE_STATE_COMING ? "Loading" :
		   "Live");
	/* Used by oprofile and other similar tools. */
	value = m->private ? NULL : mod->core_layout.base;
	seq_printf(m, " 0x%px", value);

	/* Taints info */
	if (mod->taints)
		seq_printf(m, " %s", module_flags(mod, buf));

	seq_puts(m, "\n");
	return 0;
}

Although the function accepts a void * p, from the code we can see that it actually points to the list entry for the module at offset 8.

The initial decompilation looks like follows:

Not very readable, is it? But since we know that p actually points to list inside struct module, we can use a shifted pointer instead:

This is already much better. The ugly expression with the next variable is caused by the fact that source_list actually stores instances of struct module_use so by changing the variable’s type we can improve the output again:

Creating shifted pointers for structures

Although shifted pointers are not limited to structure members, it is the most common use case, and thus we implemented a UI feature to make their creation easier.

In the decompiler, untyped variables and void pointers have a context menu item “Convert to struct *…”. When invoked, the dialog shows a list of structures (and unions) available in the local type library so you can easily create a pointer to it without typing manually. But in addition to simple struct pointers, you can create a shifted pointer by entering a non-zero delta value in the “Pointer shift value” field.

  
Because the original pointer had type void *, the shifted pointer retained it, so you may need to change the final type to get proper decompilation (in our example, struct list_head *__shifted(module,8) p).

If you want to practice this, here’s the 7.6 IDB with the function described: vmlinux_trimmed.elf.i64. To save space, it’s been trimmed to only include the function in question and its direct dependencies. To get the full kernel with symbols, see the post on DWARF info loading.