diff options
Diffstat (limited to 'com32/elflink')
| -rw-r--r-- | com32/elflink/Makefile | 104 | ||||
| -rw-r--r-- | com32/elflink/Makefile.user | 57 | ||||
| -rw-r--r-- | com32/elflink/README | 24 | ||||
| -rw-r--r-- | com32/elflink/TODO | 1 | ||||
| -rw-r--r-- | com32/elflink/elf_module.c | 887 | ||||
| -rw-r--r-- | com32/elflink/elf_module.h | 84 | ||||
| -rw-r--r-- | com32/elflink/elf_utils.c | 70 | ||||
| -rw-r--r-- | com32/elflink/elf_utils.h | 33 | ||||
| -rw-r--r-- | com32/elflink/elflink.c | 6 | ||||
| -rw-r--r-- | com32/elflink/elftest.c | 101 | ||||
| -rw-r--r-- | com32/elflink/hello_def.c | 16 | ||||
| -rw-r--r-- | com32/elflink/hello_ref.c | 26 | ||||
| -rw-r--r-- | com32/elflink/linux_list.h | 463 |
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 |