Index: kernel/generic/src/lib/elf.c =================================================================== --- kernel/generic/src/lib/elf.c (revision 1167520724b9b526c27b67f2d4bc447ef626240c) +++ kernel/generic/src/lib/elf.c (revision 1167520724b9b526c27b67f2d4bc447ef626240c) @@ -0,0 +1,225 @@ +/* + * Copyright (C) 2006 Sergey Bondari + * Copyright (C) 2006 Jakub Jermar + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup generic + * @{ + */ + +/** + * @file + * @brief Kernel ELF loader. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +static char *error_codes[] = { + "no error", + "invalid image", + "address space error", + "incompatible image", + "unsupported image type", + "irrecoverable error" +}; + +static int segment_header(elf_segment_header_t *entry, elf_header_t *elf, as_t *as); +static int section_header(elf_section_header_t *entry, elf_header_t *elf, as_t *as); +static int load_segment(elf_segment_header_t *entry, elf_header_t *elf, as_t *as); + +/** ELF loader + * + * @param header Pointer to ELF header in memory + * @param as Created and properly mapped address space + * @return EE_OK on success + */ +int elf_load(elf_header_t *header, as_t * as) +{ + int i, rc; + + /* Identify ELF */ + if (header->e_ident[EI_MAG0] != ELFMAG0 || header->e_ident[EI_MAG1] != ELFMAG1 || + header->e_ident[EI_MAG2] != ELFMAG2 || header->e_ident[EI_MAG3] != ELFMAG3) { + return EE_INVALID; + } + + /* Identify ELF compatibility */ + if (header->e_ident[EI_DATA] != ELF_DATA_ENCODING || header->e_machine != ELF_MACHINE || + header->e_ident[EI_VERSION] != EV_CURRENT || header->e_version != EV_CURRENT || + header->e_ident[EI_CLASS] != ELF_CLASS) { + return EE_INCOMPATIBLE; + } + + if (header->e_phentsize != sizeof(elf_segment_header_t)) + return EE_INCOMPATIBLE; + + if (header->e_shentsize != sizeof(elf_section_header_t)) + return EE_INCOMPATIBLE; + + /* Check if the object type is supported. */ + if (header->e_type != ET_EXEC) + return EE_UNSUPPORTED; + + /* Walk through all segment headers and process them. */ + for (i = 0; i < header->e_phnum; i++) { + rc = segment_header(&((elf_segment_header_t *)(((uint8_t *) header) + header->e_phoff))[i], header, as); + if (rc != EE_OK) + return rc; + } + + /* Inspect all section headers and proccess them. */ + for (i = 0; i < header->e_shnum; i++) { + rc = section_header(&((elf_section_header_t *)(((uint8_t *) header) + header->e_shoff))[i], header, as); + if (rc != EE_OK) + return rc; + } + + return EE_OK; +} + +/** Print error message according to error code. + * + * @param rc Return code returned by elf_load(). + * + * @return NULL terminated description of error. + */ +char *elf_error(int rc) +{ + ASSERT(rc < sizeof(error_codes)/sizeof(char *)); + + return error_codes[rc]; +} + +/** Process segment header. + * + * @param entry Segment header. + * @param elf ELF header. + * @param as Address space into wich the ELF is being loaded. + * + * @return EE_OK on success, error code otherwise. + */ +static int segment_header(elf_segment_header_t *entry, elf_header_t *elf, as_t *as) +{ + switch (entry->p_type) { + case PT_NULL: + case PT_PHDR: + break; + case PT_LOAD: + return load_segment(entry, elf, as); + break; + case PT_DYNAMIC: + case PT_INTERP: + case PT_SHLIB: + case PT_NOTE: + case PT_LOPROC: + case PT_HIPROC: + default: + return EE_UNSUPPORTED; + break; + } + return EE_OK; +} + +/** Load segment described by program header entry. + * + * @param entry Program header entry describing segment to be loaded. + * @param elf ELF header. + * @param as Address space into wich the ELF is being loaded. + * + * @return EE_OK on success, error code otherwise. + */ +int load_segment(elf_segment_header_t *entry, elf_header_t *elf, as_t *as) +{ + as_area_t *a; + int flags = 0; + mem_backend_data_t backend_data; + + backend_data.elf = elf; + backend_data.segment = entry; + + if (entry->p_align > 1) { + if ((entry->p_offset % entry->p_align) != (entry->p_vaddr % entry->p_align)) { + return EE_INVALID; + } + } + + if (entry->p_flags & PF_X) + flags |= AS_AREA_EXEC; + if (entry->p_flags & PF_W) + flags |= AS_AREA_WRITE; + if (entry->p_flags & PF_R) + flags |= AS_AREA_READ; + flags |= AS_AREA_CACHEABLE; + + /* + * Check if the virtual address starts on page boundary. + */ + if (ALIGN_UP(entry->p_vaddr, PAGE_SIZE) != entry->p_vaddr) + return EE_UNSUPPORTED; + + a = as_area_create(as, flags, entry->p_memsz, entry->p_vaddr, AS_AREA_ATTR_NONE, + &elf_backend, &backend_data); + if (!a) + return EE_MEMORY; + + /* + * The segment will be mapped on demand by elf_page_fault(). + */ + + return EE_OK; +} + +/** Process section header. + * + * @param entry Segment header. + * @param elf ELF header. + * @param as Address space into wich the ELF is being loaded. + * + * @return EE_OK on success, error code otherwise. + */ +static int section_header(elf_section_header_t *entry, elf_header_t *elf, as_t *as) +{ + switch (entry->sh_type) { + default: + break; + } + + return EE_OK; +} + +/** @} + */ Index: kernel/generic/src/lib/func.c =================================================================== --- kernel/generic/src/lib/func.c (revision 1167520724b9b526c27b67f2d4bc447ef626240c) +++ kernel/generic/src/lib/func.c (revision 1167520724b9b526c27b67f2d4bc447ef626240c) @@ -0,0 +1,196 @@ +/* + * Copyright (C) 2001-2004 Jakub Jermar + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup generic + * @{ + */ + +/** + * @file + * @brief Miscellaneous functions. + */ + +#include +#include +#include +#include +#include +#include +#include + +atomic_t haltstate = {0}; /**< Halt flag */ + + +/** Halt wrapper + * + * Set halt flag and halt the cpu. + * + */ +void halt() +{ +#ifdef CONFIG_DEBUG + bool rundebugger = false; + +// TODO test_and_set not defined on all arches +// if (!test_and_set(&haltstate)) + if (!atomic_get(&haltstate)) { + atomic_set(&haltstate, 1); + rundebugger = true; + } +#else + atomic_set(&haltstate, 1); +#endif + + interrupts_disable(); +#ifdef CONFIG_DEBUG + if (rundebugger) { + printf("\n"); + kconsole("panic"); /* Run kconsole as a last resort to user */ + } +#endif + if (CPU) + printf("cpu%d: halted\n", CPU->id); + else + printf("cpu: halted\n"); + cpu_halt(); +} + +/** Return number of characters in a string. + * + * @param str NULL terminated string. + * + * @return Number of characters in str. + */ +size_t strlen(const char *str) +{ + int i; + + for (i = 0; str[i]; i++) + ; + + return i; +} + +/** Compare two NULL terminated strings + * + * Do a char-by-char comparison of two NULL terminated strings. + * The strings are considered equal iff they consist of the same + * characters on the minimum of their lengths and specified maximal + * length. + * + * @param src First string to compare. + * @param dst Second string to compare. + * @param len Maximal length for comparison. + * + * @return 0 if the strings are equal, -1 if first is smaller, 1 if second smaller. + * + */ +int strncmp(const char *src, const char *dst, size_t len) +{ + int i; + + i = 0; + for (;*src && *dst && i < len;src++,dst++,i++) { + if (*src < *dst) + return -1; + if (*src > *dst) + return 1; + } + if (i == len || *src == *dst) + return 0; + if (!*src) + return -1; + return 1; +} + +/** Copy NULL terminated string. + * + * Copy at most 'len' characters from string 'src' to 'dest'. + * If 'src' is shorter than 'len', '\0' is inserted behind the + * last copied character. + * + * @param src Source string. + * @param dest Destination buffer. + * @param len Size of destination buffer. + */ +void strncpy(char *dest, const char *src, size_t len) +{ + int i; + for (i = 0; i < len; i++) { + if (!(dest[i] = src[i])) + return; + } + dest[i-1] = '\0'; +} + +/** Convert ascii representation to unative_t + * + * Supports 0x for hexa & 0 for octal notation. + * Does not check for overflows, does not support negative numbers + * + * @param text Textual representation of number + * @return Converted number or 0 if no valid number ofund + */ +unative_t atoi(const char *text) +{ + int base = 10; + unative_t result = 0; + + if (text[0] == '0' && text[1] == 'x') { + base = 16; + text += 2; + } else if (text[0] == '0') + base = 8; + + while (*text) { + if (base != 16 && \ + ((*text >= 'A' && *text <= 'F' ) + || (*text >='a' && *text <='f'))) + break; + if (base == 8 && *text >='8') + break; + + if (*text >= '0' && *text <= '9') { + result *= base; + result += *text - '0'; + } else if (*text >= 'A' && *text <= 'F') { + result *= base; + result += *text - 'A' + 10; + } else if (*text >= 'a' && *text <= 'f') { + result *= base; + result += *text - 'a' + 10; + } else + break; + text++; + } + + return result; +} + +/** @} + */ Index: kernel/generic/src/lib/memstr.c =================================================================== --- kernel/generic/src/lib/memstr.c (revision 1167520724b9b526c27b67f2d4bc447ef626240c) +++ kernel/generic/src/lib/memstr.c (revision 1167520724b9b526c27b67f2d4bc447ef626240c) @@ -0,0 +1,119 @@ +/* + * Copyright (C) 2001-2004 Jakub Jermar + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup generic + * @{ + */ + +/** + * @file + * @brief Memory string operations. + * + * This file provides architecture independent functions + * to manipulate blocks of memory. These functions + * are optimized as much as generic functions of + * this type can be. However, architectures are + * free to provide even more optimized versions of these + * functions. + */ + +#include +#include +#include + +/** Copy block of memory + * + * Copy cnt bytes from src address to dst address. + * The copying is done word-by-word and then byte-by-byte. + * The source and destination memory areas cannot overlap. + * + * @param src Origin address to copy from. + * @param dst Origin address to copy to. + * @param cnt Number of bytes to copy. + * + */ +void *_memcpy(void * dst, const void *src, size_t cnt) +{ + int i, j; + + if (ALIGN_UP((uintptr_t) src, sizeof(unative_t)) != (uintptr_t) src || + ALIGN_UP((uintptr_t) dst, sizeof(unative_t)) != (uintptr_t) dst) { + for (i = 0; i < cnt; i++) + ((uint8_t *) dst)[i] = ((uint8_t *) src)[i]; + } else { + + for (i = 0; i < cnt/sizeof(unative_t); i++) + ((unative_t *) dst)[i] = ((unative_t *) src)[i]; + + for (j = 0; j < cnt%sizeof(unative_t); j++) + ((uint8_t *)(((unative_t *) dst) + i))[j] = ((uint8_t *)(((unative_t *) src) + i))[j]; + } + + return (char *)src; +} + +/** Fill block of memory + * + * Fill cnt bytes at dst address with the value x. + * The filling is done byte-by-byte. + * + * @param dst Origin address to fill. + * @param cnt Number of bytes to fill. + * @param x Value to fill. + * + */ +void _memsetb(uintptr_t dst, size_t cnt, uint8_t x) +{ + int i; + uint8_t *p = (uint8_t *) dst; + + for(i=0; i +#include +#include +#include + +#define EBUFSIZE 32 + +void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot); +void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot); + +/** Quicksort wrapper + * + * This is only a wrapper that takes care of memory allocations for storing + * the pivot and temporary elements for generic quicksort algorithm. + * + * This function _can_ sleep + * + * @param data Pointer to data to be sorted. + * @param n Number of elements to be sorted. + * @param e_size Size of one element. + * @param cmp Comparator function. + * + */ +void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) +{ + uint8_t buf_tmp[EBUFSIZE]; + uint8_t buf_pivot[EBUFSIZE]; + void * tmp = buf_tmp; + void * pivot = buf_pivot; + + if (e_size > EBUFSIZE) { + pivot = (void *) malloc(e_size, 0); + tmp = (void *) malloc(e_size, 0); + } + + _qsort(data, n, e_size, cmp, tmp, pivot); + + if (e_size > EBUFSIZE) { + free(tmp); + free(pivot); + } +} + +/** Quicksort + * + * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers. + * + * @param data Pointer to data to be sorted. + * @param n Number of elements to be sorted. + * @param e_size Size of one element. + * @param cmp Comparator function. + * @param tmp Pointer to scratch memory buffer e_size bytes long. + * @param pivot Pointer to scratch memory buffer e_size bytes long. + * + */ +void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot) +{ + if (n > 4) { + int i = 0, j = n - 1; + + memcpy(pivot, data, e_size); + + while (1) { + while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++; + while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--; + if (i EBUFSIZE) { + slot = (void *) malloc(e_size, 0); + } + + _bubblesort(data, n, e_size, cmp, slot); + + if (e_size > EBUFSIZE) { + free(slot); + } +} + +/** Bubblesort + * + * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer. + * + * @param data Pointer to data to be sorted. + * @param n Number of elements to be sorted. + * @param e_size Size of one element. + * @param cmp Comparator function. + * @param slot Pointer to scratch memory buffer e_size bytes long. + * + */ +void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot) +{ + bool done = false; + void * p; + + while (!done) { + done = true; + for (p = data; p < data + e_size * (n - 1); p = p + e_size) { + if (cmp(p, p + e_size) == 1) { + memcpy(slot, p, e_size); + memcpy(p, p + e_size, e_size); + memcpy(p + e_size, slot, e_size); + done = false; + } + } + } + +} + +/* + * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b + */ +int int_cmp(void * a, void * b) +{ + return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0; +} + +int uint8_t_cmp(void * a, void * b) +{ + return (* (uint8_t *) a > * (uint8_t *)b) ? 1 : (*(uint8_t *)a < * (uint8_t *)b) ? -1 : 0; +} + +int uint16_t_cmp(void * a, void * b) +{ + return (* (uint16_t *) a > * (uint16_t *)b) ? 1 : (*(uint16_t *)a < * (uint16_t *)b) ? -1 : 0; +} + +int uint32_t_cmp(void * a, void * b) +{ + return (* (uint32_t *) a > * (uint32_t *)b) ? 1 : (*(uint32_t *)a < * (uint32_t *)b) ? -1 : 0; +} + +/** @} + */