aboutsummaryrefslogtreecommitdiffstats
path: root/com32/elflink
diff options
context:
space:
mode:
Diffstat (limited to 'com32/elflink')
-rw-r--r--com32/elflink/Makefile104
-rw-r--r--com32/elflink/Makefile.user57
-rw-r--r--com32/elflink/README24
-rw-r--r--com32/elflink/TODO1
-rw-r--r--com32/elflink/elf_module.c887
-rw-r--r--com32/elflink/elf_module.h84
-rw-r--r--com32/elflink/elf_utils.c70
-rw-r--r--com32/elflink/elf_utils.h33
-rw-r--r--com32/elflink/elflink.c6
-rw-r--r--com32/elflink/elftest.c101
-rw-r--r--com32/elflink/hello_def.c16
-rw-r--r--com32/elflink/hello_ref.c26
-rw-r--r--com32/elflink/linux_list.h463
13 files changed, 1872 insertions, 0 deletions
diff --git a/com32/elflink/Makefile b/com32/elflink/Makefile
new file mode 100644
index 00000000..1151c677
--- /dev/null
+++ b/com32/elflink/Makefile
@@ -0,0 +1,104 @@
+## -----------------------------------------------------------------------
+##
+## Copyright 2001-2008 H. Peter Anvin - All Rights Reserved
+##
+## This program is free software; you can redistribute it and/or modify
+## it under the terms of the GNU General Public License as published by
+## the Free Software Foundation, Inc., 53 Temple Place Ste 330,
+## Boston MA 02111-1307, USA; either version 2 of the License, or
+## (at your option) any later version; incorporated herein by reference.
+##
+## -----------------------------------------------------------------------
+
+##
+## COM32 standard modules
+##
+
+TMPFILE = $(shell mktemp /tmp/gcc_ok.XXXXXX)
+CC = gcc
+
+gcc_ok = $(shell tmpf=$(TMPFILE); if $(CC) $(1) -c -x c /dev/null -o $$tmpf 2>/dev/null; \
+ then echo $(1); else echo $(2); fi; rm -f $$tmpf)
+
+M32 := $(call gcc_ok,-m32,) $(call gcc_ok,-fno-stack-protector,)
+
+LD = ld -m elf_i386
+AR = ar
+NASM = nasm
+NASMOPT = -O9999
+RANLIB = ranlib
+CFLAGS = $(M32) -mregparm=3 -DREGPARM=3 -W -Wall -march=i386 -Os \
+ -fomit-frame-pointer -D__COM32__ \
+ -nostdinc -iwithprefix include \
+ -I../libutil/include -I../include \
+ -Wp,-MT,$@,-MD,$(dir $@).$(notdir $@).d
+LNXCFLAGS = -W -Wall -O -g -I../libutil/include
+LNXSFLAGS = -g
+LNXLDFLAGS = -g
+SFLAGS = -D__COM32__ -march=i386
+LDFLAGS = -T ../lib/com32.ld
+OBJCOPY = objcopy
+PPMTOLSS16 = ../ppmtolss16
+LIBGCC := $(shell $(CC) --print-libgcc)
+LIBS = ../libutil/libutil_com.a ../lib/libcom32.a $(LIBGCC)
+LNXLIBS = ../libutil/libutil_lnx.a
+
+.SUFFIXES: .lss .c .o .elf .c32 .lnx
+
+BINDIR = /usr/bin
+LIBDIR = /usr/lib
+DATADIR = /usr/share
+AUXDIR = $(DATADIR)/syslinux
+INCDIR = /usr/include
+COM32DIR = $(AUXDIR)/com32
+
+MODULES = elflink.c32
+
+TESTFILES =
+
+all: $(MODULES) $(TESTFILES)
+
+.PRECIOUS: %.o
+%.o: %.S
+ $(CC) $(SFLAGS) -c -o $@ $<
+
+.PRECIOUS: %.o
+%.o: %.c
+ $(CC) $(CFLAGS) -c -o $@ $<
+
+.PRECIOUS: %.elf
+%.elf: %.o $(LIBS)
+ $(LD) $(LDFLAGS) -o $@ $^
+
+.PRECIOUS: %.lo
+%.lo: %.S
+ $(CC) $(LNXSFLAGS) -c -o $@ $<
+
+.PRECIOUS: %.lo
+%.lo: %.c
+ $(CC) $(LNXCFLAGS) -c -o $@ $<
+
+.PRECIOUS: %.lnx
+%.lnx: %.lo $(LNXLIBS)
+ $(CC) $(LNXLDFLAGS) -o $@ $^
+
+%.c32: %.elf
+ $(OBJCOPY) -O binary $< $@
+
+elflink.elf : elflink.o elf_module.o elf_utils.o $(LIBS)
+ $(LD) $(LDFLAGS) -o $@ $^
+
+tidy dist:
+ rm -f *.o *.lo *.a *.lst *.elf .*.d
+
+clean: tidy
+ rm -f *.lss *.c32 *.lnx *.com
+
+spotless: clean
+ rm -f *~ \#*
+
+install: all
+ mkdir -m 755 -p $(INSTALLROOT)$(AUXDIR)
+ install -m 644 $(MODULES) $(INSTALLROOT)$(AUXDIR)
+
+-include .*.d
diff --git a/com32/elflink/Makefile.user b/com32/elflink/Makefile.user
new file mode 100644
index 00000000..e800d6c6
--- /dev/null
+++ b/com32/elflink/Makefile.user
@@ -0,0 +1,57 @@
+## Builds a simple user-space application that tests the basic functionality
+## of the ELF linking routines.
+
+## License would go here
+
+########
+# Tools
+
+CC = gcc
+
+RM = rm -f
+
+################
+# Build options
+
+CFLAGS = -g3 -O0 -Wall -DELF_USERSPACE_TEST
+
+LDFLAGS =
+
+##################
+# Generated files
+
+# Test executable name
+TESTPROG = elftest
+
+
+###############
+# Make targets
+.PHONY: all test-prog test-module clean
+
+all: test-prog test-module
+
+
+# The testing user-space application
+test-prog: $(TESTPROG)
+
+$(TESTPROG): elftest.o elf_module.o elf_utils.o
+ $(CC) -o $@ $^
+
+
+# The shared module to test on
+test-module: hello_def.so hello_ref.so
+
+
+hello_def.so: hello_def.o
+ $(CC) -shared -o $@ $^
+
+hello_ref.so: hello_ref.o
+ $(CC) -shared -o $@ $^
+
+
+# Cleanup target
+clean:
+ -$(RM) *.o
+ -$(RM) $(TESTPROG)
+ -$(RM) *.so
+
diff --git a/com32/elflink/README b/com32/elflink/README
new file mode 100644
index 00000000..324a8c25
--- /dev/null
+++ b/com32/elflink/README
@@ -0,0 +1,24 @@
+SYSLINUX ELF Module Loading Support
+===================================
+
+This file will contain any relevant information regarding building, integrating
+and testing ELF module loading support in SYSLINUX.
+
+
+Initial Development
+===================
+
+As the ELF modules handling code matures, building and testing will be done
+separately from the main SYSLINUX building flow. I have created a Makefile
+target that build an user space executable that tests the ELF loading code on
+a given ELF object.
+
+Run:
+
+ make test
+
+in the current directory to build the test application, then run:
+
+ ./elftest
+
+to perform the testing.
diff --git a/com32/elflink/TODO b/com32/elflink/TODO
new file mode 100644
index 00000000..19cc04ac
--- /dev/null
+++ b/com32/elflink/TODO
@@ -0,0 +1 @@
+* Create a macro for reporting debugging information.
diff --git a/com32/elflink/elf_module.c b/com32/elflink/elf_module.c
new file mode 100644
index 00000000..000ec0b1
--- /dev/null
+++ b/com32/elflink/elf_module.c
@@ -0,0 +1,887 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <elf.h>
+
+#include "linux_list.h"
+#include "elf_module.h"
+#include "elf_utils.h"
+
+// Performs an operation and jumps to a given label if an error occurs
+#define CHECKED(res, expr, error) \
+ do { \
+ (res) = (expr); \
+ if ((res) < 0) \
+ goto error; \
+ } while (0)
+
+#define MIN(x,y) (((x) < (y)) ? (x) : (y))
+#define MAX(x,y) (((x) > (y)) ? (x) : (y))
+
+// The list of loaded modules
+static LIST_HEAD(modules);
+
+
+// User-space debugging routines
+#ifdef ELF_USERSPACE_TEST
+static void print_elf_ehdr(Elf32_Ehdr *ehdr) {
+ int i;
+
+ printf("Identification:\t");
+ for (i=0; i < EI_NIDENT; i++) {
+ printf("%d ", ehdr->e_ident[i]);
+ }
+ printf("\n");
+ printf("Type:\t\t%u\n", ehdr->e_type);
+ printf("Machine:\t%u\n", ehdr->e_machine);
+ printf("Version:\t%u\n", ehdr->e_version);
+ printf("Entry:\t\t0x%08x\n", ehdr->e_entry);
+ printf("PHT Offset:\t0x%08x\n", ehdr->e_phoff);
+ printf("SHT Offset:\t0x%08x\n", ehdr->e_shoff);
+ printf("Flags:\t\t%u\n", ehdr->e_flags);
+ printf("Header size:\t%u (Structure size: %u)\n", ehdr->e_ehsize,
+ sizeof(Elf32_Ehdr));
+}
+
+static void print_elf_symbols(struct elf_module *module) {
+ Elf32_Word *bkt = module->hash_table + 2;
+ Elf32_Word *chn = module->hash_table + 2 + module->hash_table[0];
+ Elf32_Word i, crt_index;
+ Elf32_Sym *crt_sym;
+
+ printf("Bucket count: %d \n", module->hash_table[0]);
+ printf("Chain count: %d (Non GNU-Hash: %d)\n", module->hash_table[1],
+ module->ghash_table[1]);
+
+ for (i = 0; i < module->hash_table[0]; i++) {
+ printf("Bucket %d:\n", i);
+ crt_index = bkt[i];
+
+ while (crt_index != STN_UNDEF) {
+ crt_sym = (Elf32_Sym*)(module->sym_table + crt_index*module->syment_size);
+
+ printf("%s\n", module->str_table + crt_sym->st_name);
+ crt_index = chn[crt_index];
+ }
+ }
+}
+#endif //ELF_USERSPACE_TEST
+
+static int image_load(struct elf_module *module) {
+ char file_name[MODULE_NAME_SIZE+3]; // Include the extension
+
+ strcpy(file_name, module->name);
+ strcat(file_name, ".so");
+
+ module->_file = fopen(file_name, "rb");
+
+ if (module->_file == NULL) {
+ perror("Could not open object file");
+ goto error;
+ }
+
+ module->_cr_offset = 0;
+
+ return 0;
+
+error:
+ if (module->_file != NULL) {
+ fclose(module->_file);
+ module->_file = NULL;
+ }
+
+ return -1;
+}
+
+
+static int image_unload(struct elf_module *module) {
+ if (module->_file != NULL) {
+ fclose(module->_file);
+ module->_file = NULL;
+ }
+ module->_cr_offset = 0;
+
+ return 0;
+}
+
+static int image_read(void *buff, size_t size, struct elf_module *module) {
+ size_t result = fread(buff, size, 1, module->_file);
+
+ if (result < 1)
+ return -1;
+
+ printf("[DBG] Read %u\n", size);
+ module->_cr_offset += size;
+ return 0;
+}
+
+static int image_skip(size_t size, struct elf_module *module) {
+ void *skip_buff = NULL;
+ size_t result;
+
+ if (size == 0)
+ return 0;
+
+ skip_buff = malloc(size);
+ result = fread(skip_buff, size, 1, module->_file);
+ free(skip_buff);
+
+ if (result < 1)
+ return -1;
+
+ printf("[DBG] Skipped %u\n", size);
+ module->_cr_offset += size;
+ return 0;
+}
+
+static int image_seek(Elf32_Off offset, struct elf_module *module) {
+ if (offset < module->_cr_offset) // Cannot seek backwards
+ return -1;
+
+ return image_skip(offset - module->_cr_offset, module);
+}
+
+
+// Initialization of the module subsystem
+int modules_init() {
+ return 0;
+}
+
+// Termination of the module subsystem
+void modules_term() {
+
+}
+
+// Allocates the structure for a new module
+struct elf_module *module_alloc(const char *name) {
+ struct elf_module *result = malloc(sizeof(struct elf_module));
+
+ memset(result, 0, sizeof(struct elf_module));
+
+ INIT_LIST_HEAD(&result->list);
+ INIT_LIST_HEAD(&result->required);
+ INIT_LIST_HEAD(&result->dependants);
+
+ strncpy(result->name, name, MODULE_NAME_SIZE);
+
+ return result;
+}
+
+static struct module_dep *module_dep_alloc(struct elf_module *module) {
+ struct module_dep *result = malloc(sizeof(struct module_dep));
+
+ INIT_LIST_HEAD (&result->list);
+
+ result->module = module;
+
+ return result;
+}
+
+struct elf_module *module_find(const char *name) {
+ struct elf_module *cr_module;
+
+ list_for_each_entry(cr_module, &modules, list) {
+ if (strcmp(cr_module->name, name) == 0)
+ return cr_module;
+ }
+
+ return NULL;
+}
+
+// Performs verifications on ELF header to assure that the open file is a
+// valid SYSLINUX ELF module.
+static int check_header(Elf32_Ehdr *elf_hdr) {
+ // Check the header magic
+ if (elf_hdr->e_ident[EI_MAG0] != ELFMAG0 ||
+ elf_hdr->e_ident[EI_MAG1] != ELFMAG1 ||
+ elf_hdr->e_ident[EI_MAG2] != ELFMAG2 ||
+ elf_hdr->e_ident[EI_MAG3] != ELFMAG3) {
+
+ fprintf(stderr, "The file is not an ELF object\n");
+ return -1;
+ }
+
+ if (elf_hdr->e_ident[EI_CLASS] != MODULE_ELF_CLASS) {
+ fprintf(stderr, "Invalid ELF class code\n");
+ return -1;
+ }
+
+ if (elf_hdr->e_ident[EI_DATA] != MODULE_ELF_DATA) {
+ fprintf(stderr, "Invalid ELF data encoding\n");
+ return -1;
+ }
+
+ if (elf_hdr->e_ident[EI_VERSION] != MODULE_ELF_VERSION ||
+ elf_hdr->e_version != MODULE_ELF_VERSION) {
+ fprintf(stderr, "Invalid ELF file version\n");
+ return -1;
+ }
+
+ if (elf_hdr->e_type != MODULE_ELF_TYPE) {
+ fprintf(stderr, "The ELF file must be a shared object\n");
+ return -1;
+ }
+
+
+ if (elf_hdr->e_machine != MODULE_ELF_MACHINE) {
+ fprintf(stderr, "Invalid ELF architecture\n");
+ return -1;
+ }
+
+ if (elf_hdr->e_phoff == 0x00000000) {
+ fprintf(stderr, "PHT missing\n");
+ return -1;
+ }
+
+ return 0;
+}
+
+/*
+ *
+ * The implementation assumes that the loadable segments are present
+ * in the PHT sorted by their offsets, so that only forward seeks would
+ * be necessary.
+ */
+static int load_segments(struct elf_module *module, Elf32_Ehdr *elf_hdr) {
+ int i;
+ int res = 0;
+ void *pht = NULL;
+ Elf32_Phdr *cr_pht;
+
+ Elf32_Addr min_addr = 0x00000000; // Min. ELF vaddr
+ Elf32_Addr max_addr = 0x00000000; // Max. ELF vaddr
+ Elf32_Word max_align = sizeof(void*); // Min. align of posix_memalign()
+ Elf32_Addr min_alloc, max_alloc; // Min. and max. aligned allocables
+
+ Elf32_Addr dyn_addr = 0x00000000;
+
+ // Get to the PHT
+ image_seek(elf_hdr->e_phoff, module);
+
+ // Load the PHT
+ pht = malloc(elf_hdr->e_phnum * elf_hdr->e_phentsize);
+ image_read(pht, elf_hdr->e_phnum * elf_hdr->e_phentsize, module);
+
+ // Compute the memory needings of the module
+ for (i=0; i < elf_hdr->e_phnum; i++) {
+ cr_pht = (Elf32_Phdr*)(pht + i * elf_hdr->e_phentsize);
+
+ switch (cr_pht->p_type) {
+ case PT_LOAD:
+ if (i == 0) {
+ min_addr = cr_pht->p_vaddr;
+ } else {
+ min_addr = MIN(min_addr, cr_pht->p_vaddr);
+ }
+
+ max_addr = MAX(max_addr, cr_pht->p_vaddr + cr_pht->p_memsz);
+ max_align = MAX(max_align, cr_pht->p_align);
+ break;
+ case PT_DYNAMIC:
+ dyn_addr = cr_pht->p_vaddr;
+ break;
+ default:
+ // Unsupported - ignore
+ break;
+ }
+ }
+
+ if (max_addr - min_addr == 0) {
+ // No loadable segments
+ fprintf(stderr, "No loadable segments found\n");
+ goto out;
+ }
+
+ if (dyn_addr == 0) {
+ fprintf(stderr, "No dynamic information segment found\n");
+ goto out;
+ }
+
+ // The minimum address that should be allocated
+ min_alloc = min_addr - (min_addr % max_align);
+
+ // The maximum address that should be allocated
+ max_alloc = max_addr - (max_addr % max_align);
+ if (max_addr % max_align > 0)
+ max_alloc += max_align;
+
+
+ if (elf_malloc(&module->module_addr,
+ max_align,
+ max_alloc-min_alloc) != 0) {
+
+ fprintf(stderr, "Could not allocate segments\n");
+ goto out;
+ }
+
+ module->base_addr = (Elf32_Addr)(module->module_addr) - min_alloc;
+ module->module_size = max_alloc - min_alloc;
+
+ // Zero-initialize the memory
+ memset(module->module_addr, 0, module->module_size);
+
+ for (i = 0; i < elf_hdr->e_phnum; i++) {
+ cr_pht = (Elf32_Phdr*)(pht + i * elf_hdr->e_phentsize);
+
+ if (cr_pht->p_type == PT_LOAD) {
+ // Copy the segment at its destination
+ if (cr_pht->p_offset < module->_cr_offset) {
+ // The segment contains data before the current offset
+ // It can be discarded without worry - it would contain only
+ // headers
+ Elf32_Off aux_off = module->_cr_offset - cr_pht->p_offset;
+
+ if (image_read(module_get_absolute(cr_pht->p_vaddr, module) + aux_off,
+ cr_pht->p_filesz - aux_off, module) < 0) {
+ res = -1;
+ goto out;
+ }
+ } else {
+ if (image_seek(cr_pht->p_offset, module) < 0) {
+ res = -1;
+ goto out;
+ }
+
+ if (image_read(module_get_absolute(cr_pht->p_vaddr, module),
+ cr_pht->p_filesz, module) < 0) {
+ res = -1;
+ goto out;
+ }
+ }
+
+ printf("Loadable segment of size 0x%08x copied from vaddr 0x%08x at 0x%08x\n",
+ cr_pht->p_filesz,
+ cr_pht->p_vaddr,
+ (Elf32_Addr)module_get_absolute(cr_pht->p_vaddr, module));
+ }
+ }
+
+ // Setup dynamic segment location
+ module->dyn_table = module_get_absolute(dyn_addr, module);
+
+ printf("Base address: 0x%08x, aligned at 0x%08x\n", module->base_addr,
+ max_align);
+ printf("Module size: 0x%08x\n", module->module_size);
+
+out:
+ // Free up allocated memory
+ if (pht != NULL)
+ free(pht);
+
+ return res;
+}
+
+static int prepare_dynlinking(struct elf_module *module) {
+ Elf32_Dyn *dyn_entry = module->dyn_table;
+
+ while (dyn_entry->d_tag != DT_NULL) {
+ switch (dyn_entry->d_tag) {
+ case DT_NEEDED:
+ // TODO: Manage dependencies here
+ break;
+ case DT_HASH:
+ module->hash_table =
+ (Elf32_Word*)module_get_absolute(dyn_entry->d_un.d_ptr, module);
+ break;
+ case DT_GNU_HASH: // TODO: Add support for this one, too (50% faster)
+ module->ghash_table =
+ (Elf32_Word*)module_get_absolute(dyn_entry->d_un.d_ptr, module);
+ break;
+ case DT_STRTAB:
+ module->str_table =
+ (char*)module_get_absolute(dyn_entry->d_un.d_ptr, module);
+ break;
+ case DT_SYMTAB:
+ module->sym_table =
+ module_get_absolute(dyn_entry->d_un.d_ptr, module);
+ break;
+ case DT_STRSZ:
+ module->strtable_size = dyn_entry->d_un.d_val;
+ break;
+ case DT_SYMENT:
+ module->syment_size = dyn_entry->d_un.d_val;
+ break;
+ case DT_PLTGOT: // The first entry in the GOT
+ module->got = module_get_absolute(dyn_entry->d_un.d_ptr, module);
+ break;
+ }
+
+ dyn_entry++;
+ }
+
+
+ return 0;
+}
+
+static int enforce_dependency(struct elf_module *req, struct elf_module *dep) {
+ struct module_dep *crt_dep;
+ struct module_dep *new_dep;
+
+ list_for_each_entry(crt_dep, &req->dependants, list) {
+ if (crt_dep->module == dep) {
+ // The dependency is already enforced
+ return 0;
+ }
+ }
+
+ new_dep = module_dep_alloc(req);
+ list_add(&new_dep->list, &dep->required);
+
+ new_dep = module_dep_alloc(dep);
+ list_add(&new_dep->list, &req->dependants);
+
+ return 0;
+}
+
+static int clear_dependency(struct elf_module *req, struct elf_module *dep) {
+ struct module_dep *crt_dep = NULL;
+ int found = 0;
+
+ list_for_each_entry(crt_dep, &req->dependants, list) {
+ if (crt_dep->module == dep) {
+ found = 1;
+ break;
+ }
+ }
+
+ if (found) {
+ list_del(&crt_dep->list);
+ free(crt_dep);
+ }
+
+ found = 0;
+
+ list_for_each_entry(crt_dep, &dep->required, list) {
+ if (crt_dep->module == req) {
+ found = 1;
+ break;
+ }
+ }
+
+ if (found) {
+ list_del(&crt_dep->list);
+ free(crt_dep);
+ }
+
+ return 0;
+}
+
+static int perform_relocation(struct elf_module *module, Elf32_Rel *rel) {
+ Elf32_Word *dest = module_get_absolute(rel->r_offset, module);
+
+ // The symbol reference index
+ Elf32_Word sym = ELF32_R_SYM(rel->r_info);
+ unsigned char type = ELF32_R_TYPE(rel->r_info);
+
+ // The symbol definition (if applicable)
+ Elf32_Sym *sym_def = NULL;
+ struct elf_module *sym_module = NULL;
+ Elf32_Addr sym_addr = 0x0;
+
+ if (sym > 0) {
+ // Find out details about the symbol
+
+ // The symbol reference
+ Elf32_Sym *sym_ref =
+ (Elf32_Sym*)(module->sym_table + sym * module->syment_size);
+
+ // The symbol definition
+ sym_def =
+ global_find_symbol(module->str_table + sym_ref->st_name,
+ &sym_module);
+
+ if (sym_def == NULL) {
+ // This should never happen
+ fprintf(stderr, "Warning: Cannot perform relocation for symbol %s\n",
+ module->str_table + sym_ref->st_name);
+ // TODO: Return an error
+ return 0;
+ }
+
+ // Compute the absolute symbol virtual address
+ sym_addr = (Elf32_Addr)module_get_absolute(sym_def->st_value, sym_module);
+
+ if (sym_module != module) {
+ // Create a dependency
+ enforce_dependency(sym_module, module);
+ }
+ }
+
+ switch (type) {
+ case R_386_NONE:
+ // Do nothing
+ break;
+ case R_386_32:
+ *dest += sym_addr;
+ break;
+ case R_386_PC32:
+ *dest += sym_addr - (Elf32_Addr)dest;
+ break;
+ case R_386_COPY:
+ if (sym_addr > 0) {
+ memcpy((void*)dest, (void*)sym_addr, sym_def->st_size);
+ }
+ break;
+ case R_386_GLOB_DAT:
+ case R_386_JMP_SLOT:
+ // Maybe TODO: Keep track of the GOT entries allocations
+ *dest = sym_addr;
+ break;
+ case R_386_RELATIVE:
+ *dest += module->base_addr;
+ break;
+ default:
+ fprintf(stderr, "Warning: Relocation type %d not supported\n", type);
+ break;
+ }
+
+ return 0;
+}
+
+static int resolve_symbols(struct elf_module *module) {
+ Elf32_Dyn *dyn_entry = module->dyn_table;
+ unsigned int i;
+ int res;
+
+ Elf32_Word plt_rel_size = 0;
+ void *plt_rel = NULL;
+
+ void *rel = NULL;
+ Elf32_Word rel_size = 0;
+ Elf32_Word rel_entry = 0;
+
+ // The current relocation
+ Elf32_Rel *crt_rel;
+
+ while (dyn_entry->d_tag != DT_NULL) {
+ switch(dyn_entry->d_tag) {
+
+ // PLT relocation information
+ case DT_PLTRELSZ:
+ plt_rel_size = dyn_entry->d_un.d_val;
+ break;
+ case DT_PLTREL:
+ if (dyn_entry->d_un.d_val != DT_REL) {
+ fprintf(stderr, "Unsupported PLT relocation\n");
+ return -1;
+ }
+ case DT_JMPREL:
+ plt_rel = module_get_absolute(dyn_entry->d_un.d_ptr, module);
+ break;
+
+ // Standard relocation information
+ case DT_REL:
+ rel = module_get_absolute(dyn_entry->d_un.d_ptr, module);
+ break;
+ case DT_RELSZ:
+ rel_size = dyn_entry->d_un.d_val;
+ break;
+ case DT_RELENT:
+ rel_entry = dyn_entry->d_un.d_val;
+ break;
+
+ // Module initialization and termination
+ case DT_INIT:
+ // TODO Implement initialization functions
+ break;
+ case DT_FINI:
+ // TODO Implement finalization functions
+ break;
+ }
+
+ dyn_entry++;
+ }
+
+ if (rel_size > 0) {
+ // Process standard relocations
+ for (i = 0; i < rel_size/rel_entry; i++) {
+ crt_rel = (Elf32_Rel*)(rel + i*rel_entry);
+
+ res = perform_relocation(module, crt_rel);
+
+ if (res < 0)
+ return res;
+ }
+
+ }
+
+ if (plt_rel_size > 0) {
+ // TODO: Permit this lazily
+ // Process PLT relocations
+ for (i = 0; i < plt_rel_size/sizeof(Elf32_Rel); i++) {
+ crt_rel = (Elf32_Rel*)(plt_rel + i*sizeof(Elf32_Rel));
+
+ res = perform_relocation(module, crt_rel);
+
+ if (res < 0)
+ return res;
+ }
+ }
+
+ return 0;
+}
+
+static int check_symbols(struct elf_module *module) {
+ unsigned int i;
+ Elf32_Sym *crt_sym, *ref_sym;
+ char *crt_name;
+ struct elf_module *crt_module;
+
+ int strong_count;
+ int weak_count;
+
+ // The chain count gives the number of symbols
+ for (i = 1; i < module->hash_table[1]; i++) {
+ crt_sym = (Elf32_Sym*)(module->sym_table + i * module->syment_size);
+ crt_name = module->str_table + crt_sym->st_name;
+
+ strong_count = 0;
+ weak_count = 0;
+
+ list_for_each_entry(crt_module, &modules, list) {
+ ref_sym = module_find_symbol(crt_name, crt_module);
+
+ // If we found a definition for our symbol...
+ if (ref_sym != NULL && ref_sym->st_shndx != SHN_UNDEF) {
+ switch (ELF32_ST_BIND(ref_sym->st_info)) {
+ case STB_GLOBAL:
+ strong_count++;
+ break;
+ case STB_WEAK:
+ weak_count++;
+ break;
+ }
+ }
+ }
+
+ if (crt_sym->st_shndx == SHN_UNDEF) {
+ // We have an undefined symbol
+ if (strong_count == 0 && weak_count == 0) {
+ fprintf(stderr, "Symbol %s is undefined\n", crt_name);
+ // TODO: Return an error
+ //return -1;
+ }
+ } else {
+ if (strong_count > 0 && ELF32_ST_BIND(ref_sym->st_info) == STB_GLOBAL) {
+ fprintf(stderr, "Warning: Symbol %s is defined more than once\n", crt_name);
+ //return -1;
+ }
+ }
+ }
+
+ return 0;
+}
+
+// Loads the module into the system
+int module_load(struct elf_module *module) {
+ int res;
+ Elf32_Ehdr elf_hdr;
+
+ // Get a mapping/copy of the ELF file in memory
+ res = image_load(module);
+
+ if (res < 0) {
+ return res;
+ }
+
+ CHECKED(res, image_read(&elf_hdr, sizeof(Elf32_Ehdr), module), error);
+
+ // Checking the header signature and members
+ CHECKED(res, check_header(&elf_hdr), error);
+
+ // DEBUG
+#ifdef ELF_USERSPACE_TEST
+ print_elf_ehdr(&elf_hdr);
+#endif // ELF_USERSPACE_TEST
+
+ // Load the segments in the memory
+ CHECKED(res, load_segments(module, &elf_hdr), error);
+ // Obtain dynamic linking information
+ CHECKED(res, prepare_dynlinking(module), error);
+
+ // DEBUG
+#ifdef ELF_USERSPACE_TEST
+ print_elf_symbols(module);
+#endif // ELF_USERSPACE_TEST
+
+ // Check the symbols for duplicates / missing definitions
+ CHECKED(res, check_symbols(module), error);
+
+ // Add the module at the beginning of the module list
+ list_add(&module->list, &modules);
+
+ // Perform the relocations
+ resolve_symbols(module);
+
+ // The file image is no longer needed
+ image_unload(module);
+
+
+ return 0;
+
+error:
+ // Remove the module from the module list (if applicable)
+ list_del_init(&module->list);
+
+ if (module->module_addr != NULL) {
+ elf_free(module->module_addr);
+ module->module_addr = NULL;
+ }
+
+ image_unload(module);
+
+ return res;
+}
+
+// Unloads the module from the system and releases all the associated memory
+int module_unload(struct elf_module *module) {
+ struct module_dep *crt_dep, *tmp;
+ // Make sure nobody needs us
+ if (!list_empty(&module->dependants)) {
+ fprintf(stderr, "Module is required by other modules.\n");
+ return -1;
+ }
+
+ // Remove any dependency information
+ list_for_each_entry_safe(crt_dep, tmp, &module->required, list) {
+ clear_dependency(crt_dep->module, module);
+ }
+
+ // Remove the module from the module list
+ list_del_init(&module->list);
+
+ // Release the loaded segments
+ elf_free(module->module_addr);
+ // Release the module structure
+ free(module);
+
+ return 0;
+}
+
+
+static Elf32_Sym *module_find_symbol_sysv(const char *name, struct elf_module *module) {
+ unsigned long h = elf_hash((const unsigned char*)name);
+ Elf32_Word *cr_word = module->hash_table;
+
+ Elf32_Word nbucket = *cr_word++;
+ cr_word++; // Skip nchain
+
+ Elf32_Word *bkt = cr_word;
+ Elf32_Word *chn = cr_word + nbucket;
+
+ Elf32_Word crt_index = bkt[h % module->hash_table[0]];
+ Elf32_Sym *crt_sym;
+
+
+ while (crt_index != STN_UNDEF) {
+ crt_sym = (Elf32_Sym*)(module->sym_table + crt_index*module->syment_size);
+
+ if (strcmp(name, module->str_table + crt_sym->st_name) == 0)
+ return crt_sym;
+
+ crt_index = chn[crt_index];
+ }
+
+ return NULL;
+}
+
+static Elf32_Sym *module_find_symbol_gnu(const char *name, struct elf_module *module) {
+ unsigned long h = elf_gnu_hash((const unsigned char*)name);
+
+ // Setup code (TODO: Optimize this by computing only once)
+ Elf32_Word *cr_word = module->ghash_table;
+ Elf32_Word nbucket = *cr_word++;
+ Elf32_Word symbias = *cr_word++;
+ Elf32_Word bitmask_nwords = *cr_word++;
+
+ if ((bitmask_nwords & (bitmask_nwords - 1)) != 0) {
+ fprintf(stderr, "Warning: Invalid GNU Hash structure\n");
+ return NULL;
+ }
+
+ Elf32_Word gnu_shift = *cr_word++;
+
+ Elf32_Addr *gnu_bitmask = (Elf32_Addr*)cr_word;
+ cr_word += MODULE_ELF_CLASS_SIZE / 32 * bitmask_nwords;
+
+ Elf32_Word *gnu_buckets = cr_word;
+ cr_word += nbucket;
+
+ Elf32_Word *gnu_chain_zero = cr_word - symbias;
+
+ // Computations
+ Elf32_Word bitmask_word = gnu_bitmask[(h / MODULE_ELF_CLASS_SIZE) &
+ (bitmask_nwords - 1)];
+
+ unsigned int hashbit1 = h & (MODULE_ELF_CLASS_SIZE - 1);
+ unsigned int hashbit2 = (h >> gnu_shift) & (MODULE_ELF_CLASS_SIZE - 1);
+
+ if ((bitmask_word >> hashbit1) & (bitmask_word >> hashbit2) & 1) {
+ unsigned long rem;
+ Elf32_Word bucket;
+
+ rem = h % nbucket;
+
+ bucket = gnu_buckets[rem];
+
+ if (bucket != 0) {
+ const Elf32_Word* hasharr = &gnu_chain_zero[bucket];
+
+ do {
+ if (((*hasharr ^ h ) >> 1) == 0) {
+ Elf32_Sym *crt_sym = (Elf32_Sym*)(module->sym_table +
+ (hasharr - gnu_chain_zero) * module->syment_size);
+
+ if (strcmp(name, module->str_table + crt_sym->st_name) == 0) {
+ return crt_sym;
+ }
+ }
+ } while ((*hasharr++ & 1u) == 0);
+ }
+ }
+
+ return NULL;
+}
+
+Elf32_Sym *module_find_symbol(const char *name, struct elf_module *module) {
+ Elf32_Sym *result = NULL;
+
+ if (module->ghash_table != NULL)
+ result = module_find_symbol_gnu(name, module);
+
+ if (result == NULL)
+ result = module_find_symbol_sysv(name, module);
+
+ return result;
+}
+
+Elf32_Sym *global_find_symbol(const char *name, struct elf_module **module) {
+ struct elf_module *crt_module;
+ Elf32_Sym *crt_sym = NULL;
+ Elf32_Sym *result = NULL;
+
+ list_for_each_entry(crt_module, &modules, list) {
+ crt_sym = module_find_symbol(name, crt_module);
+
+ if (crt_sym != NULL && crt_sym->st_shndx != SHN_UNDEF) {
+ switch (ELF32_ST_BIND(crt_sym->st_info)) {
+ case STB_GLOBAL:
+ if (module != NULL) {
+ *module = crt_module;
+ }
+ return crt_sym;
+ case STB_WEAK:
+ // Consider only the first weak symbol
+ if (result == NULL) {
+ if (module != NULL) {
+ *module = crt_module;
+ }
+ result = crt_sym;
+ }
+ break;
+ }
+ }
+ }
+
+ return result;
+}
diff --git a/com32/elflink/elf_module.h b/com32/elflink/elf_module.h
new file mode 100644
index 00000000..1454ee71
--- /dev/null
+++ b/com32/elflink/elf_module.h
@@ -0,0 +1,84 @@
+#ifndef ELF_MODULE_H_
+#define ELF_MODULE_H_
+
+#include <stdio.h>
+#include <elf.h>
+#include <stdint.h>
+#include "linux_list.h"
+
+#define MODULE_NAME_SIZE 64
+
+#define MODULE_ELF_CLASS ELFCLASS32
+#define MODULE_ELF_CLASS_SIZE 32
+#define MODULE_ELF_DATA ELFDATA2LSB
+#define MODULE_ELF_VERSION EV_CURRENT
+#define MODULE_ELF_TYPE ET_DYN
+#define MODULE_ELF_MACHINE EM_386
+
+
+typedef int (*module_init_func)();
+typedef void (*module_exit_func)();
+
+// Structure encapsulating a module loaded in memory
+struct elf_module {
+ char name[MODULE_NAME_SIZE]; // The module name
+
+ struct list_head required; // Head of the required modules list
+ struct list_head dependants; // Head of module dependants list
+ struct list_head list; // The list entry in the module list
+
+ module_init_func init_func; // The initialization entry point
+ module_exit_func exit_func; // The module finalization code
+
+
+ void *module_addr; // The module location in the memory
+ Elf32_Addr base_addr; // The base address of the module
+ Elf32_Word module_size; // The module size in memory
+
+ Elf32_Word *hash_table; // The symbol hash table
+ Elf32_Word *ghash_table; // The GNU style hash table
+ char *str_table; // The string table
+ void *sym_table; // The symbol table
+ void *got; // The Global Offset Table
+ Elf32_Dyn *dyn_table; // Dynamic loading information table
+
+ Elf32_Word strtable_size; // The size of the string table
+ Elf32_Word syment_size; // The size of a symbol entry
+
+
+ // Transient - Data available while the module is loading
+ FILE *_file; // The file object of the open file
+ Elf32_Off _cr_offset; // The current offset in the open file
+};
+
+// Structure encapsulating a module dependency need
+struct module_dep {
+ struct list_head list; // The list entry in the dependency list
+
+ struct elf_module *module;
+};
+
+// Initialization of the module subsystem
+extern int modules_init();
+// Termination of the module subsystem
+extern void modules_term();
+
+// Allocates the structure for a new module
+extern struct elf_module *module_alloc(const char *name);
+
+// Loads the module into the system
+extern int module_load(struct elf_module *module);
+
+// Unloads the module from the system and releases all the associated memory
+extern int module_unload(struct elf_module *module);
+
+extern struct elf_module *module_find(const char *name);
+
+extern Elf32_Sym *module_find_symbol(const char *name, struct elf_module *module);
+extern Elf32_Sym *global_find_symbol(const char *name, struct elf_module **module);
+
+static inline void *module_get_absolute(Elf32_Addr addr, struct elf_module *module) {
+ return (void*)(module->base_addr + addr);
+}
+
+#endif /*ELF_MODULE_H_*/
diff --git a/com32/elflink/elf_utils.c b/com32/elflink/elf_utils.c
new file mode 100644
index 00000000..be320772
--- /dev/null
+++ b/com32/elflink/elf_utils.c
@@ -0,0 +1,70 @@
+#include <stdlib.h>
+#include <errno.h>
+
+#include "elf_utils.h"
+
+unsigned long elf_hash(const unsigned char *name) {
+ unsigned long h = 0;
+ unsigned long g;
+
+ while (*name) {
+ h = (h << 4) + *name++;
+ if ((g = h & 0xF0000000))
+ h ^= g >> 24;
+
+ h &= ~g;
+ }
+
+ return h;
+}
+
+unsigned long elf_gnu_hash(const unsigned char *name) {
+ unsigned long h = 5381;
+ unsigned char c;
+
+ for (c = *name; c != '\0'; c = *++name) {
+ h = h * 33 + c;
+ }
+
+ return h & 0xFFFFFFFF;
+}
+
+
+struct memalign_info {
+ void *start_addr;
+ char data[0];
+};
+
+int elf_malloc(void **memptr, size_t alignment, size_t size) {
+ void *start_addr = NULL;
+ struct memalign_info *info;
+
+ if ((alignment & (alignment - 1)) != 0)
+ return EINVAL;
+ if (alignment % sizeof(void*) != 0)
+ return EINVAL;
+
+ start_addr = malloc(size + (alignment > sizeof(struct memalign_info) ?
+ alignment : sizeof(struct memalign_info)));
+
+ if (start_addr == NULL)
+ return ENOMEM;
+
+
+ info = (struct memalign_info*)(start_addr -
+ ((unsigned long)start_addr % alignment) +
+ alignment - sizeof(struct memalign_info));
+
+ info->start_addr = start_addr;
+
+ *memptr = info->data;
+
+ return 0;
+}
+
+void elf_free(void *memptr) {
+ struct memalign_info *info = (struct memalign_info*)(memptr -
+ sizeof(struct memalign_info));
+
+ free(info->start_addr);
+}
diff --git a/com32/elflink/elf_utils.h b/com32/elflink/elf_utils.h
new file mode 100644
index 00000000..b8df660e
--- /dev/null
+++ b/com32/elflink/elf_utils.h
@@ -0,0 +1,33 @@
+#ifndef ELF_UTILS_H_
+#define ELF_UTILS_H_
+
+#include <elf.h>
+#include <stdlib.h>
+
+// Returns a pointer to the ELF header structure
+static inline Elf32_Ehdr *elf_get_header(void *elf_image) {
+ return (Elf32_Ehdr*)elf_image;
+}
+
+// Returns a pointer to the first entry in the Program Header Table
+static inline Elf32_Phdr *elf_get_pht(void *elf_image) {
+ Elf32_Ehdr *elf_hdr = elf_get_header(elf_image);
+
+ return (Elf32_Phdr*)((Elf32_Off)elf_hdr + elf_hdr->e_phoff);
+}
+
+// Returns the element with the given index in the PTH
+static inline Elf32_Phdr *elf_get_ph(void *elf_image, int index) {
+ Elf32_Phdr *elf_pht = elf_get_pht(elf_image);
+ Elf32_Ehdr *elf_hdr = elf_get_header(elf_image);
+
+ return (Elf32_Phdr*)((Elf32_Off)elf_pht + index * elf_hdr->e_phentsize);
+}
+
+extern unsigned long elf_hash(const unsigned char *name);
+extern unsigned long elf_gnu_hash(const unsigned char *name);
+
+extern int elf_malloc(void **memptr, size_t alignment, size_t size);
+extern void elf_free(void *memptr);
+
+#endif /*ELF_UTILS_H_*/
diff --git a/com32/elflink/elflink.c b/com32/elflink/elflink.c
new file mode 100644
index 00000000..22b0db5d
--- /dev/null
+++ b/com32/elflink/elflink.c
@@ -0,0 +1,6 @@
+#include "elf_module.h"
+
+int main(int argc, char **argv) {
+ return 0;
+}
+
diff --git a/com32/elflink/elftest.c b/com32/elflink/elftest.c
new file mode 100644
index 00000000..0a38bbe6
--- /dev/null
+++ b/com32/elflink/elftest.c
@@ -0,0 +1,101 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+#include "elf_module.h"
+
+void print_usage() {
+ fprintf(stderr, "Usage:\n");
+ fprintf(stderr, "\telftest objfile ...\n");
+}
+
+void test_hello() {
+ int i;
+
+ struct elf_module *module;
+ Elf32_Sym *symbol;
+
+ symbol = global_find_symbol("undef_func", &module);
+
+ void (*undef_func)(int) = module_get_absolute(symbol->st_value, module);
+
+ symbol = global_find_symbol("test_func", &module);
+
+ int (*test_func)(void) = module_get_absolute(symbol->st_value, module);
+
+ undef_func(0);
+
+ for (i=0; i < 10; i++) {
+ printf("%d\n", test_func());
+ }
+}
+
+int main(int argc, char **argv) {
+ int res;
+ int i;
+ struct elf_module *module;
+ const char *module_name = NULL;
+
+ // Skip program name
+ argc--;
+ argv++;
+
+ if (argc < 1) {
+ print_usage();
+ return 1;
+ }
+
+ res = modules_init();
+
+ if (res < 0) {
+ fprintf(stderr, "Could not initialize module subsystem\n");
+ exit(1);
+ }
+
+ for (i=0; i < argc; i++){
+ module_name = argv[i];
+
+ module = module_alloc(module_name);
+
+ if (module == NULL) {
+ fprintf(stderr, "Could not allocate the module\n");
+ goto error;
+ }
+
+ res = module_load(module);
+
+ if (res < 0) {
+ fprintf(stderr, "Could not load the module\n");
+ goto error;
+ }
+
+ }
+
+ test_hello();
+
+ for (i=argc-1; i >= 0; i--) {
+ module_name = argv[i];
+ module = module_find(module_name);
+
+ res = module_unload(module);
+
+ if (res < 0) {
+ fprintf(stderr, "Could not unload the module\n");
+ goto error;
+ }
+ }
+
+ modules_term();
+
+ return 0;
+
+error:
+ modules_term();
+
+ return 1;
+}
diff --git a/com32/elflink/hello_def.c b/com32/elflink/hello_def.c
new file mode 100644
index 00000000..2ad60233
--- /dev/null
+++ b/com32/elflink/hello_def.c
@@ -0,0 +1,16 @@
+
+int undef_symbol;
+
+void undef_func(int param) {
+ undef_symbol = 100;
+}
+
+static int hello_init(void) {
+ // Do nothing
+
+ return 0;
+}
+
+static void hello_exit(void) {
+ // Do nothing
+}
diff --git a/com32/elflink/hello_ref.c b/com32/elflink/hello_ref.c
new file mode 100644
index 00000000..f7b798b4
--- /dev/null
+++ b/com32/elflink/hello_ref.c
@@ -0,0 +1,26 @@
+// A simple Hello World ELF module
+
+// TODO: Define some macros that would put the initialization and termination
+// functions in a separate section (suggestion: .init and .fini)
+
+// Undefined symbol
+extern int undef_symbol;
+
+int exported_symbol;
+
+// Undefined function
+extern void undef_func(int param);
+
+int test_func(void) {
+ return undef_symbol++;
+}
+
+static int hello_init(void) {
+ undef_symbol++;
+
+ return 0;
+}
+
+static void hello_exit(void) {
+ undef_func(undef_symbol);
+}
diff --git a/com32/elflink/linux_list.h b/com32/elflink/linux_list.h
new file mode 100644
index 00000000..3b92e254
--- /dev/null
+++ b/com32/elflink/linux_list.h
@@ -0,0 +1,463 @@
+// This list structure implementation is adapted from the list implementation
+// on the Linux kernel.
+
+// Original source:
+// http://git.kernel.org/?p=linux/kernel/git/stable/linux-2.6.25.y.git;a=blob_plain;f=include/linux/list.h;hb=HEAD
+
+#ifndef _LINUX_LIST_H
+#define _LINUX_LIST_H
+
+/*
+ * Simple doubly linked list implementation.
+ *
+ * Some of the internal functions ("__xxx") are useful when
+ * manipulating whole lists rather than single entries, as
+ * sometimes we already know the next/prev entries and we can
+ * generate better code by using them directly rather than
+ * using the generic single-entry routines.
+ */
+
+#include <stdlib.h>
+#include <stddef.h>
+
+struct list_head {
+ struct list_head *next, *prev;
+};
+
+#define LIST_HEAD_INIT(name) { &(name), &(name) }
+
+#define LIST_HEAD(name) \
+ struct list_head name = LIST_HEAD_INIT(name)
+
+static inline void INIT_LIST_HEAD(struct list_head *list)
+{
+ list->next = list;
+ list->prev = list;
+}
+
+/**
+ * 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) );})
+
+
+/*
+ * Insert a new entry between two known consecutive entries.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_add(struct list_head *new,
+ struct list_head *prev,
+ struct list_head *next)
+{
+ next->prev = new;
+ new->next = next;
+ new->prev = prev;
+ prev->next = new;
+}
+
+/**
+ * list_add - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+static inline void list_add(struct list_head *new, struct list_head *head)
+{
+ __list_add(new, head, head->next);
+}
+
+
+
+/**
+ * list_add_tail - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it before
+ *
+ * Insert a new entry before the specified head.
+ * This is useful for implementing queues.
+ */
+static inline void list_add_tail(struct list_head *new, struct list_head *head)
+{
+ __list_add(new, head->prev, head);
+}
+
+
+/*
+ * Delete a list entry by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_del(struct list_head * prev, struct list_head * next)
+{
+ next->prev = prev;
+ prev->next = next;
+}
+
+/**
+ * list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty() on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+static inline void list_del(struct list_head *entry)
+{
+ __list_del(entry->prev, entry->next);
+ entry->next = NULL;
+ entry->prev = NULL;
+}
+
+/**
+ * list_replace - replace old entry by new one
+ * @old : the element to be replaced
+ * @new : the new element to insert
+ *
+ * If @old was empty, it will be overwritten.
+ */
+static inline void list_replace(struct list_head *old,
+ struct list_head *new)
+{
+ new->next = old->next;
+ new->next->prev = new;
+ new->prev = old->prev;
+ new->prev->next = new;
+}
+
+static inline void list_replace_init(struct list_head *old,
+ struct list_head *new)
+{
+ list_replace(old, new);
+ INIT_LIST_HEAD(old);
+}
+
+/**
+ * list_del_init - deletes entry from list and reinitialize it.
+ * @entry: the element to delete from the list.
+ */
+static inline void list_del_init(struct list_head *entry)
+{
+ __list_del(entry->prev, entry->next);
+ INIT_LIST_HEAD(entry);
+}
+
+/**
+ * list_move - delete from one list and add as another's head
+ * @list: the entry to move
+ * @head: the head that will precede our entry
+ */
+static inline void list_move(struct list_head *list, struct list_head *head)
+{
+ __list_del(list->prev, list->next);
+ list_add(list, head);
+}
+
+/**
+ * list_move_tail - delete from one list and add as another's tail
+ * @list: the entry to move
+ * @head: the head that will follow our entry
+ */
+static inline void list_move_tail(struct list_head *list,
+ struct list_head *head)
+{
+ __list_del(list->prev, list->next);
+ list_add_tail(list, head);
+}
+
+/**
+ * list_is_last - tests whether @list is the last entry in list @head
+ * @list: the entry to test
+ * @head: the head of the list
+ */
+static inline int list_is_last(const struct list_head *list,
+ const struct list_head *head)
+{
+ return list->next == head;
+}
+
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static inline int list_empty(const struct list_head *head)
+{
+ return head->next == head;
+}
+
+/**
+ * list_empty_careful - tests whether a list is empty and not being modified
+ * @head: the list to test
+ *
+ * Description:
+ * tests whether a list is empty _and_ checks that no other CPU might be
+ * in the process of modifying either member (next or prev)
+ *
+ * NOTE: using list_empty_careful() without synchronization
+ * can only be safe if the only activity that can happen
+ * to the list entry is list_del_init(). Eg. it cannot be used
+ * if another CPU could re-list_add() it.
+ */
+static inline int list_empty_careful(const struct list_head *head)
+{
+ struct list_head *next = head->next;
+ return (next == head) && (next == head->prev);
+}
+
+static inline void __list_splice(struct list_head *list,
+ struct list_head *head)
+{
+ struct list_head *first = list->next;
+ struct list_head *last = list->prev;
+ struct list_head *at = head->next;
+
+ first->prev = head;
+ head->next = first;
+
+ last->next = at;
+ at->prev = last;
+}
+
+/**
+ * list_splice - join two lists
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ */
+static inline void list_splice(struct list_head *list, struct list_head *head)
+{
+ if (!list_empty(list))
+ __list_splice(list, head);
+}
+
+/**
+ * list_splice_init - join two lists and reinitialise the emptied list.
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ *
+ * The list at @list is reinitialised
+ */
+static inline void list_splice_init(struct list_head *list,
+ struct list_head *head)
+{
+ if (!list_empty(list)) {
+ __list_splice(list, head);
+ INIT_LIST_HEAD(list);
+ }
+}
+
+/**
+ * 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_struct 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_struct 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_for_each - iterate over a list
+ * @pos: the &struct list_head to use as a loop cursor.
+ * @head: the head for your list.
+ */
+#define list_for_each(pos, head) \
+ for (pos = (head)->next; pos != (head); \
+ pos = pos->next)
+
+/**
+ * __list_for_each - iterate over a list
+ * @pos: the &struct list_head to use as a loop cursor.
+ * @head: the head for your list.
+ *
+ * This variant differs from list_for_each() in that it's the
+ * simplest possible list iteration code, no prefetching is done.
+ * Use this for code that knows the list to be very short (empty
+ * or 1 entry) most of the time.
+ */
+#define __list_for_each(pos, head) \
+ for (pos = (head)->next; pos != (head); pos = pos->next)
+
+/**
+ * list_for_each_prev - iterate over a list backwards
+ * @pos: the &struct list_head to use as a loop cursor.
+ * @head: the head for your list.
+ */
+#define list_for_each_prev(pos, head) \
+ for (pos = (head)->prev; pos != (head); \
+ pos = pos->prev)
+
+/**
+ * list_for_each_safe - iterate over a list safe against removal of list entry
+ * @pos: the &struct list_head to use as a loop cursor.
+ * @n: another &struct list_head to use as temporary storage
+ * @head: the head for your list.
+ */
+#define list_for_each_safe(pos, n, head) \
+ for (pos = (head)->next, n = pos->next; pos != (head); \
+ pos = n, n = pos->next)
+
+/**
+ * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
+ * @pos: the &struct list_head to use as a loop cursor.
+ * @n: another &struct list_head to use as temporary storage
+ * @head: the head for your list.
+ */
+#define list_for_each_prev_safe(pos, n, head) \
+ for (pos = (head)->prev, n = pos->prev; \
+ pos != (head); \
+ pos = n, n = pos->prev)
+
+/**
+ * list_for_each_entry - iterate over list of given type
+ * @pos: the type * to use as a loop cursor.
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ */
+#define list_for_each_entry(pos, head, member) \
+ for (pos = list_entry((head)->next, typeof(*pos), member); \
+ &pos->member != (head); \
+ pos = list_entry(pos->member.next, typeof(*pos), member))
+
+/**
+ * list_for_each_entry_reverse - iterate backwards over list of given type.
+ * @pos: the type * to use as a loop cursor.
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ */
+#define list_for_each_entry_reverse(pos, head, member) \
+ for (pos = list_entry((head)->prev, typeof(*pos), member); \
+ &pos->member != (head); \
+ pos = list_entry(pos->member.prev, typeof(*pos), member))
+
+/**
+ * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
+ * @pos: the type * to use as a start point
+ * @head: the head of the list
+ * @member: the name of the list_struct within the struct.
+ *
+ * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
+ */
+#define list_prepare_entry(pos, head, member) \
+ ((pos) ? : list_entry(head, typeof(*pos), member))
+
+/**
+ * list_for_each_entry_continue - continue iteration over list of given type
+ * @pos: the type * to use as a loop cursor.
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ *
+ * Continue to iterate over list of given type, continuing after
+ * the current position.
+ */
+#define list_for_each_entry_continue(pos, head, member) \
+ for (pos = list_entry(pos->member.next, typeof(*pos), member); \
+ &pos->member != (head); \
+ pos = list_entry(pos->member.next, typeof(*pos), member))
+
+/**
+ * list_for_each_entry_continue_reverse - iterate backwards from the given point
+ * @pos: the type * to use as a loop cursor.
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ *
+ * Start to iterate over list of given type backwards, continuing after
+ * the current position.
+ */
+#define list_for_each_entry_continue_reverse(pos, head, member) \
+ for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
+ &pos->member != (head); \
+ pos = list_entry(pos->member.prev, typeof(*pos), member))
+
+/**
+ * list_for_each_entry_from - iterate over list of given type from the current point
+ * @pos: the type * to use as a loop cursor.
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ *
+ * Iterate over list of given type, continuing from current position.
+ */
+#define list_for_each_entry_from(pos, head, member) \
+ for (; &pos->member != (head); \
+ pos = list_entry(pos->member.next, typeof(*pos), member))
+
+/**
+ * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ */
+#define list_for_each_entry_safe(pos, n, head, member) \
+ for (pos = list_entry((head)->next, typeof(*pos), member), \
+ n = list_entry(pos->member.next, typeof(*pos), member); \
+ &pos->member != (head); \
+ pos = n, n = list_entry(n->member.next, typeof(*n), member))
+
+/**
+ * list_for_each_entry_safe_continue
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ *
+ * Iterate over list of given type, continuing after current point,
+ * safe against removal of list entry.
+ */
+#define list_for_each_entry_safe_continue(pos, n, head, member) \
+ for (pos = list_entry(pos->member.next, typeof(*pos), member), \
+ n = list_entry(pos->member.next, typeof(*pos), member); \
+ &pos->member != (head); \
+ pos = n, n = list_entry(n->member.next, typeof(*n), member))
+
+/**
+ * list_for_each_entry_safe_from
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ *
+ * Iterate over list of given type from current point, safe against
+ * removal of list entry.
+ */
+#define list_for_each_entry_safe_from(pos, n, head, member) \
+ for (n = list_entry(pos->member.next, typeof(*pos), member); \
+ &pos->member != (head); \
+ pos = n, n = list_entry(n->member.next, typeof(*n), member))
+
+/**
+ * list_for_each_entry_safe_reverse
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @head: the head for your list.
+ * @member: the name of the list_struct within the struct.
+ *
+ * Iterate backwards over list of given type, safe against removal
+ * of list entry.
+ */
+#define list_for_each_entry_safe_reverse(pos, n, head, member) \
+ for (pos = list_entry((head)->prev, typeof(*pos), member), \
+ n = list_entry(pos->member.prev, typeof(*pos), member); \
+ &pos->member != (head); \
+ pos = n, n = list_entry(n->member.prev, typeof(*n), member))
+
+
+#endif