diff options
Diffstat (limited to 'cfe/cfe/lib')
| -rw-r--r-- | cfe/cfe/lib/lib_arena.c | 389 | ||||
| -rw-r--r-- | cfe/cfe/lib/lib_malloc.c | 620 | ||||
| -rw-r--r-- | cfe/cfe/lib/lib_misc.c | 229 | ||||
| -rw-r--r-- | cfe/cfe/lib/lib_printf.c | 442 | ||||
| -rw-r--r-- | cfe/cfe/lib/lib_qsort.c | 88 | ||||
| -rw-r--r-- | cfe/cfe/lib/lib_queue.c | 219 | ||||
| -rw-r--r-- | cfe/cfe/lib/lib_string.c | 386 | ||||
| -rw-r--r-- | cfe/cfe/lib/lib_string2.c | 96 |
8 files changed, 2469 insertions, 0 deletions
diff --git a/cfe/cfe/lib/lib_arena.c b/cfe/cfe/lib/lib_arena.c new file mode 100644 index 0000000..41867dc --- /dev/null +++ b/cfe/cfe/lib/lib_arena.c @@ -0,0 +1,389 @@ +/* ********************************************************************* + * Broadcom Common Firmware Environment (CFE) + * + * Arena Manager File lib_arena.c + * + * This module manages the _arena_, a sorted linked list of + * memory regions and attributes. We use this to keep track + * of physical memory regions and what is assigned to them. + * + * Author: Mitch Lichtenberg (mpl@broadcom.com) + * + ********************************************************************* + * + * Copyright 2000,2001,2002,2003 + * Broadcom Corporation. All rights reserved. + * + * This software is furnished under license and may be used and + * copied only in accordance with the following terms and + * conditions. Subject to these conditions, you may download, + * copy, install, use, modify and distribute modified or unmodified + * copies of this software in source and/or binary form. No title + * or ownership is transferred hereby. + * + * 1) Any source code used, modified or distributed must reproduce + * and retain this copyright notice and list of conditions + * as they appear in the source file. + * + * 2) No right is granted to use any trade name, trademark, or + * logo of Broadcom Corporation. The "Broadcom Corporation" + * name may not be used to endorse or promote products derived + * from this software without the prior written permission of + * Broadcom Corporation. + * + * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED + * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR + * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT + * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN + * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR 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), EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************* */ + +#include "lib_types.h" +#include "lib_queue.h" +#include "lib_arena.h" +#include "lib_malloc.h" + +/* ********************************************************************* + * arena_print(arena,msg) + * + * Debug routine to print out an arena entry + * + * Input parameters: + * arena - arena descriptor + * msg - heading message + * + * Return value: + * nothing + ********************************************************************* */ + +#ifdef _TESTPROG_ +static void arena_print(arena_t *arena,char *msg) +{ + arena_node_t *node; + queue_t *qb; + + printf("%s\n",msg); + + for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list); + qb = qb->q_next) { + node = (arena_node_t *) qb; + + printf("Start %5I64d End %5I64d Type %d\n", + node->an_address, + node->an_address+node->an_length, + node->an_type); + + } + +} +#endif + +/* ********************************************************************* + * arena_init(arena,physmembase,physmemsize) + * + * Initialize an arena descriptor. The arena is typically + * created to describe the entire physical memory address space. + * + * Input parameters: + * arena - arena descriptor + * physmembase - base of region to manage (usually 0) + * physmemsize - size of region to manage (typically maxint) + * + * Return value: + * nothing + ********************************************************************* */ + +void arena_init(arena_t *arena,uint64_t physmembase,uint64_t physmemsize) +{ + arena_node_t *an = NULL; + + an = (arena_node_t *) KMALLOC(sizeof(arena_node_t),sizeof(uint64_t)); + + /* XXX check return value */ + + arena->arena_base = physmembase; + arena->arena_size = physmemsize; + + an->an_address = physmembase; + an->an_length = physmemsize; + an->an_type = 0; + an->an_descr = NULL; + + q_init(&(arena->arena_list)); + q_enqueue(&(arena->arena_list),(queue_t *) an); +} + + +/* ********************************************************************* + * arena_find(arena,pt) + * + * Locate the arena node containing a particular point in the + * address space. This routine walks the list and finds the node + * whose address range contains the specified point. + * + * Input parameters: + * arena - arena descriptor + * pt - point to look for + * + * Return value: + * arena node pointer, or NULL if no node found + ********************************************************************* */ + +static arena_node_t *arena_find(arena_t *arena,uint64_t pt) +{ + queue_t *qb; + arena_node_t *an; + + for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list); + qb = qb->q_next) { + an = (arena_node_t *) qb; + + if ((pt >= an->an_address) && + (pt < (an->an_address + an->an_length))) return an; + + } + + return NULL; +} + +/* ********************************************************************* + * arena_split(arena,splitpoint) + * + * Split the node containing the specified point. When we carve + * the arena up, we split the arena at the points on the edges + * of the new region, change their types, and then coalesce the + * arena. This handles the "split" part of that process. + * + * Input parameters: + * arena - arena descriptor + * splitpoint - address to split arena at + * + * Return value: + * 0 if ok + * -1 if could not split + ********************************************************************* */ + +static int arena_split(arena_t *arena,uint64_t splitpoint) +{ + arena_node_t *node; + arena_node_t *newnode; + + /* + * Don't need to split if it's the *last* address in the arena + */ + + if (splitpoint == (arena->arena_base+arena->arena_size)) return 0; + + /* + * Find the block that contains the split point. + */ + + node = arena_find(arena,splitpoint); + if (node == NULL) return -1; /* should not happen */ + + /* + * If the address matches exactly, don't need to split + */ + if (node->an_address == splitpoint) return 0; + + /* + * Allocate a new node and adjust the length of the node we're + * splitting. + */ + + newnode = (arena_node_t *) KMALLOC(sizeof(arena_node_t),sizeof(uint64_t)); + + newnode->an_length = node->an_length - (splitpoint - node->an_address); + node->an_length = splitpoint - node->an_address; + newnode->an_address = splitpoint; + newnode->an_type = node->an_type; + + /* + * Put the new node in the arena + */ + + q_enqueue(node->an_next.q_next,(queue_t *) newnode); + + return 0; +} + +/* ********************************************************************* + * arena_coalesce(arena) + * + * Coalesce the arena, merging regions that have the same type + * together. After coalescing, no two adjacent nodes will + * have the same type. + * + * Input parameters: + * arena - arena descriptor + * + * Return value: + * nothing + ********************************************************************* */ + +static void arena_coalesce(arena_t *arena) +{ + arena_node_t *node; + arena_node_t *nextnode; + int removed; + queue_t *qb; + + do { + removed = 0; + for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list); + qb = qb->q_next) { + + node = (arena_node_t *) qb; + nextnode = (arena_node_t *) node->an_next.q_next; + + if ((queue_t *) nextnode == &(arena->arena_list)) break; + + if (node->an_type == nextnode->an_type) { + node->an_length += nextnode->an_length; + q_dequeue((queue_t *) nextnode); + KFREE(nextnode); + removed++; + } + } + } while (removed > 0); +} + + +/* ********************************************************************* + * arena_markrange(arena,address,length,type,descr) + * + * Mark a region in the arena, changing the types of nodes and + * splitting nodes as necessary. This routine is called for + * each region we want to add. The order of marking regions is + * important, since new marks overwrite old ones. Therefore, you + * could mark a whole range as DRAM, and then mark sub-regions + * within that as used by firmware. + * + * Input parameters: + * arena - arena descriptor + * address,length - region to mark + * type - type code for region + * descr - text description of region (optional) + * + * Return value: + * 0 if ok + * -1 if error + ********************************************************************* */ + +int arena_markrange(arena_t *arena,uint64_t address,uint64_t length,int type,char *descr) +{ + queue_t *qb; + arena_node_t *node; + + /* + * Range check the region we want to mark + */ + + if ((address < arena->arena_base) || + ((address+length) > (arena->arena_base + arena->arena_size))) { + return -1; + } + + /* + * Force the arena to be split at the two points at the + * beginning and end of the range we want. If we have + * problems, coalesce the arena again and get out. + */ + + if (arena_split(arena,address) < 0) { + /* don't need to coalesce, we didn't split */ + return -1; + } + if (arena_split(arena,(address+length)) < 0) { + /* recombine nodes split above */ + arena_coalesce(arena); + return -1; + } + + /* + * Assuming we've split the arena at the beginning and ending + * split points, we'll never mark any places outside the range + * specified in the "Address,length" args. + */ + + for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list); + qb = qb->q_next) { + node = (arena_node_t *) qb; + + if ((node->an_address >= address) && + ((node->an_address + node->an_length) <= (address+length))) { + node->an_type = type; + node->an_descr = descr; + } + } + + /* + * Now, coalesce adjacent pieces with the same type back together again + */ + + arena_coalesce(arena); + + return 0; +} + + + +/* ********************************************************************* + * main(argc,argv) + * + * Test program. + * + * Input parameters: + * argc,argv - guess + * + * Return value: + * nothing + ********************************************************************* */ + +#ifdef _TESTPROG_ +void main(int argc,char *argv[]) +{ + arena_t arena; + + arena_init(&arena,0,1024); +#if 0 + arena_print(&arena,"empty arena------------"); + + arena_split(&arena,5); + arena_print(&arena,"split at 5-------------"); + + arena_split(&arena,300); + arena_print(&arena,"split at 300-----------"); + + arena_split(&arena,100); + arena_print(&arena,"split at 100-----------"); + + arena_coalesce(&arena); + arena_print(&arena,"coalesced again--------"); + + arena_markrange(&arena,100,50,1); + arena_print(&arena,"addrange 100-150-------"); + arena_markrange(&arena,10,50,1); + arena_print(&arena,"addrange 10-60---------"); + arena_markrange(&arena,1000,24,3); + arena_print(&arena,"addrange 1000-1023-----"); +#endif + + arena_markrange(&arena,100,10,1); + arena_markrange(&arena,120,10,2); + arena_markrange(&arena,140,10,3); + arena_print(&arena,"Before big markrange---------"); + + arena_markrange(&arena,50,200,4); + arena_print(&arena,"after big markrange---------"); + +} +#endif diff --git a/cfe/cfe/lib/lib_malloc.c b/cfe/cfe/lib/lib_malloc.c new file mode 100644 index 0000000..f7e33b2 --- /dev/null +++ b/cfe/cfe/lib/lib_malloc.c @@ -0,0 +1,620 @@ +/* ********************************************************************* + * Broadcom Common Firmware Environment (CFE) + * + * Local memory manager File: cfe_malloc.c + * + * This routine is used to manage memory allocated within the + * firmware. You give it a chunk of memory to manage, and then + * these routines manage suballocations from there. + * + * Author: Mitch Lichtenberg (mpl@broadcom.com) + * + ********************************************************************* + * + * Copyright 2000,2001,2002,2003 + * Broadcom Corporation. All rights reserved. + * + * This software is furnished under license and may be used and + * copied only in accordance with the following terms and + * conditions. Subject to these conditions, you may download, + * copy, install, use, modify and distribute modified or unmodified + * copies of this software in source and/or binary form. No title + * or ownership is transferred hereby. + * + * 1) Any source code used, modified or distributed must reproduce + * and retain this copyright notice and list of conditions + * as they appear in the source file. + * + * 2) No right is granted to use any trade name, trademark, or + * logo of Broadcom Corporation. The "Broadcom Corporation" + * name may not be used to endorse or promote products derived + * from this software without the prior written permission of + * Broadcom Corporation. + * + * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED + * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR + * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT + * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN + * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR 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), EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************* */ + +#ifdef TESTPROG +#include <stdio.h> +#include <malloc.h> +#include <stdlib.h> +#endif + +#include "lib_types.h" +#include "lib_printf.h" +#include "lib_malloc.h" + + +/* ********************************************************************* + * Constants + ********************************************************************* */ + +#define MEMNODE_SEAL 0xFAAFA123 /* just some random constant */ +#define MINBLKSIZE 64 + +/* ********************************************************************* + * Types + ********************************************************************* */ + +typedef enum { memnode_free = 0, memnode_alloc } memnode_status_t; + +typedef struct memnode_s { + unsigned int seal; + struct memnode_s *next; /* pointer to next node */ + unsigned int length; /* length of the entire data section */ + memnode_status_t status; /* alloc/free status */ + unsigned char *data; /* points to actual user data */ + void *memnodeptr; /* memnode back pointer (see comments) */ +} memnode_t; + +struct mempool_s { + memnode_t *root; /* pointer to root node */ + unsigned char *base; /* base of memory region */ + unsigned int length; /* size of memory region */ +}; + +#define memnode_data(t,m) (t) (((memnode_t *) (m))+1) + +/* ********************************************************************* + * Globals + ********************************************************************* */ + +mempool_t kmempool; /* default pool */ + +/* ********************************************************************* + * kmeminit(pool,buffer,length) + * + * Initialize the memory manager, given a pointer to an area + * of memory and a size. This routine simply initializes the + * root node to be a single block of empty space. + * + * Input parameters: + * pool - pool pointer + * buffer - beginning of buffer area, must be pointer-aligned + * length - length of buffer area + * + * Return value: + * nothing + ********************************************************************* */ + + +void kmeminit(mempool_t *pool,unsigned char *buffer,int length) +{ + pool->root = (memnode_t *) buffer; + pool->root->seal = MEMNODE_SEAL; + pool->root->length = length - sizeof(memnode_t); + pool->root->data = memnode_data(unsigned char *,pool->root); + pool->root->status = memnode_free; + pool->root->next = NULL; + + pool->base = buffer; + pool->length = length; +} + + +/* ********************************************************************* + * kmempoolbase(pool) + * + * Returns the base address of the specified memory pool + * + * Input parameters: + * pool - pool pointer + * + * Return value: + * pointer to beginning of pool's memory + ********************************************************************* */ +void *kmempoolbase(mempool_t *pool) +{ + return pool->base; +} + +/* ********************************************************************* + * kmempoolsize(pool) + * + * Returns the total size of the specified memory pool + * + * Input parameters: + * pool - pool pointer + * + * Return value: + * size of pool in bytes + ********************************************************************* */ + +int kmempoolsize(mempool_t *pool) +{ + return pool->length; +} + +/* ********************************************************************* + * kmemcompact(pool) + * + * Compact the memory blocks, coalescing consectutive free blocks + * on the list. + * + * Input parameters: + * pool - pool descriptor + * + * Return value: + * nothing + ********************************************************************* */ + +static void kmemcompact(mempool_t *pool) +{ + memnode_t *m; + int compacted; + + do { + compacted = 0; + + for (m = pool->root; m; m = m->next) { + + /* Check seal to be sure that we're doing ok */ + + if (m->seal != MEMNODE_SEAL) { +#ifdef TESTPROG + printf("Memory list corrupted!\n"); +#endif + return; + } + + /* + * If we're not on the last block and both this + * block and the next one are free, combine them + */ + + if (m->next && + (m->status == memnode_free) && + (m->next->status == memnode_free)) { + m->length += sizeof(memnode_t) + m->next->length; + m->next->seal = 0; + m->next = m->next->next; + compacted++; + } + + /* Keep going till we make a pass without doing anything. */ + } + } while (compacted > 0); +} + + +/* ********************************************************************* + * kfree(ptr) + * + * Return some memory to the pool. + * + * Input parameters: + * ptr - pointer to something allocated via kmalloc() + * + * Return value: + * nothing + ********************************************************************* */ + +void kfree(mempool_t *pool,void *ptr) +{ + memnode_t **backptr; + memnode_t *m; + + if (((unsigned char *) ptr < pool->base) || + ((unsigned char *) ptr >= (pool->base+pool->length))) { +#ifdef TESTPROG + printf("Pointer %08X does not belong to pool %08X\n",ptr,pool); +#endif + return; + } + + backptr = (memnode_t **) (((unsigned char *) ptr) - sizeof(memnode_t *)); + m = *backptr; + + if (m->seal != MEMNODE_SEAL) { +#ifdef TESTPROG + printf("Invalid node freed: %08X\n",m); +#endif + return; + } + + m->status = memnode_free; + + kmemcompact(pool); +} + +/* ********************************************************************* + * lib_outofmemory() + * + * Called when we run out of memory. + * XXX replace with something real someday + * + * Input parameters: + * nothing + * + * Return value: + * nothing + ********************************************************************* */ + +void lib_outofmemory(void); +void lib_outofmemory(void) +{ + xprintf("PANIC: out of memory!\n"); +} + +/* ********************************************************************* + * kmalloc(pool,size,align) + * + * Allocate some memory from the pool. + * + * Input parameters: + * pool - pool structure + * size - size of item to allocate + * align - alignment (must be zero or a power of 2) + * + * Return value: + * pointer to data, or NULL if no memory left + ********************************************************************* */ + +void *kmalloc(mempool_t *pool,unsigned int size,unsigned int align) +{ + memnode_t *m; + memnode_t *newm; + memnode_t **backptr; + uintptr_t daddr = 0; + uintptr_t realsize = 0; + uintptr_t extra; + uintptr_t blkend; + uintptr_t ptralign; + + /* + * Everything should be aligned by at least the + * size of an int64 + */ + + ptralign = (uintptr_t) align; + if (ptralign < sizeof(void *)) ptralign = sizeof(uint64_t); + + /* + * Everything should be at least a multiple of the + * size of a pointer. + */ + + if (size == 0) size = sizeof(void *); + if (size & (sizeof(void *)-1)) { + size += sizeof(void *); + size &= ~(sizeof(void *)-1); + } + + /* + * Find a memnode at least big enough to hold the storage we + * want. + */ + + for (m = pool->root; m; m = m->next) { + + if (m->status == memnode_alloc) continue; + + /* + * If we wanted a particular alignment, we will + * need to adjust the size. + */ + + daddr = memnode_data(uintptr_t,m); + extra = 0; + if (daddr & (ptralign-1)) { + extra = size + (ptralign - (daddr & (ptralign-1))); + } + realsize = size + extra; + + if (m->length < realsize) continue; + break; + } + + /* + * If m is null, there's no memory left. + */ + + if (m == NULL) { + lib_outofmemory(); + return NULL; + } + + /* + * Otherwise, use this block. Calculate the address of the data + * to preserve the alignment. + */ + + if (daddr & (ptralign-1)) { + daddr += ptralign; + daddr &= ~(ptralign-1); + } + + /* Mark this node as allocated. */ + + m->data = (unsigned char *) daddr; + m->status = memnode_alloc; + + /* + * Okay, this is ugly. Store a pointer to the original + * memnode just before what we've allocated. It's guaranteed + * to be aligned at least well enough for this pointer. + * If for some reason the memnode was already exactly + * aligned, backing up will put us inside the memnode + * structure itself... that's why the memnodeptr field + * is there, as a placeholder for this eventuality. + */ + + backptr = (memnode_t **) (m->data - sizeof(memnode_t *)); + *backptr = m; + + /* + * See if we need to split it. + * Don't bother to split if the resulting size will be + * less than MINBLKSIZE bytes + */ + + if (m->length - realsize < MINBLKSIZE) { + return m->data; + } + + /* + * Split this block. Align the address on a pointer-size + * boundary. + */ + + daddr += size; + if (daddr & (uintptr_t)(sizeof(void *)-1)) { + daddr += (uintptr_t)sizeof(void *); + daddr &= ~(uintptr_t)(sizeof(void *)-1); + } + + blkend = memnode_data(uintptr_t,m) + (uintptr_t)(m->length); + + newm = (memnode_t *) daddr; + + newm->next = m->next; + m->length = (unsigned int) (daddr - memnode_data(uintptr_t,m)); + m->next = newm; + m->status = memnode_alloc; + newm->seal = MEMNODE_SEAL; + newm->data = memnode_data(unsigned char *,newm); + newm->length = (unsigned int) (blkend - memnode_data(uintptr_t,newm)); + newm->status = memnode_free; + + return m->data; +} + + +int kmemstats(mempool_t *pool,memstats_t *stats) +{ + memnode_t *m; + memnode_t **backptr; + uintptr_t daddr; + + stats->mem_totalbytes = pool->length; + stats->mem_allocbytes = 0; + stats->mem_freebytes = 0; + stats->mem_allocnodes = 0; + stats->mem_freenodes = 0; + stats->mem_largest = 0; + + for (m = pool->root; m; m = m->next) { + if (m->status) { + stats->mem_allocnodes++; + stats->mem_allocbytes += m->length; + } + else { + stats->mem_freenodes++; + stats->mem_freebytes += m->length; + if (m->length > stats->mem_largest) { + stats->mem_largest = m->length; + } + } + + daddr = memnode_data(uintptr_t,m); + if (m->seal != MEMNODE_SEAL) { + return -1; + } + if (m->next && ((daddr + m->length) != (uintptr_t) m->next)) { + return -1; + } + if (m->next && (m->next < m)) { + return -1; + } + if (m->data < (unsigned char *) m) { + return -1; + } + if (m->status == memnode_alloc) { + backptr = (memnode_t **) (m->data - sizeof(void *)); + if (*backptr != m) { + return -1; + } + } + } + + return 0; +} + + +/* ********************************************************************* + * kmemchk() + * + * Check the consistency of the memory pool. + * + * Input parameters: + * pool - pool pointer + * + * Return value: + * 0 - pool is consistent + * -1 - pool is corrupt + ********************************************************************* */ + +#ifdef TESTPROG +int kmemchk(mempool_t *pool,int verbose) +{ + memnode_t *m; + memnode_t **backptr; + unsigned int daddr; + + for (m = pool->root; m; m = m->next) { + if (verbose) { + printf("%08X: Next=%08X Len=%5u %s Data=%08X ", + m,m->next,m->length, + m->status ? "alloc" : "free ", + m->data); + } + daddr = memnode_data(uintptr_t,m); + if (m->seal != MEMNODE_SEAL) { + if (verbose) printf("BadSeal "); + else return -1; + } + if (m->next && (daddr + m->length != (unsigned int) m->next)) { + if (verbose) printf("BadLength "); + else return -1; + } + if (m->next && (m->next < m)) { + if (verbose) printf("BadOrder "); + else return -1; + } + if (m->data < (unsigned char *) m) { + if (verbose) printf("BadData "); + else return -1; + } + if (m->status == memnode_alloc) { + backptr = (memnode_t **) (m->data - sizeof(void *)); + if (*backptr != m) { + if (verbose) printf("BadBackPtr "); + else return -1; + } + } + if (verbose) printf("\n"); + } + + return 0; +} + + +#define MEMSIZE 1024*1024 + +unsigned char *ptrs[4096]; +unsigned int sizes[4096]; + +/* ********************************************************************* + * main(argc,argv) + * + * Test program for the memory allocator + * + * Input parameters: + * argc,argv + * + * Return value: + * nothing + ********************************************************************* */ + + +void main(int argc,char *argv[]) +{ + unsigned char *mem; + int items = 0; + int idx; + int size; + int totalsize = 0; + int nfree,freecnt; + mempool_t *pool = &kmempool; + + mem = malloc(MEMSIZE); + kmeminit(pool,mem,MEMSIZE); + + items = 0; + + for (;;) { + + for (;;) { + if (items == 4096) break; + size = rand() % 1024; + ptrs[items] = kmalloc(pool,size,1<<(rand() & 7)); + if (!ptrs[items]) break; + sizes[items] = size; + items++; + totalsize += size; + } + + printf("%d items allocated, %d total bytes\n",items,totalsize); + + if (kmemchk(pool,0) < 0) { + kmemchk(pool,1); + exit(1); + } + + /* Scramble the pointers */ + idx = items - 1; + + while (idx) { + if (rand() & 2) { + mem = ptrs[0]; + ptrs[0] = ptrs[idx]; + ptrs[idx] = mem; + + nfree = sizes[0]; + sizes[0] = sizes[idx]; + sizes[idx] = nfree; + } + idx--; + } + + /* now free a random number of elements */ + + nfree = rand() % items; + freecnt = 0; + + for (idx = nfree; idx < items; idx++) { + kfree(pool,ptrs[idx]); + totalsize -= sizes[idx]; + freecnt++; + ptrs[idx] = NULL; + sizes[idx] = 0; + if (kmemchk(pool,0) < 0) { + kmemchk(pool,1); + exit(1); + } + } + + items -= freecnt; + + printf("."); + + } + + kmemchk(pool,1); + + exit(0); +} + +#endif /* TESTPROG */ diff --git a/cfe/cfe/lib/lib_misc.c b/cfe/cfe/lib/lib_misc.c new file mode 100644 index 0000000..e5a2a02 --- /dev/null +++ b/cfe/cfe/lib/lib_misc.c @@ -0,0 +1,229 @@ +/* ********************************************************************* + * Broadcom Common Firmware Environment (CFE) + * + * Misc. library routines File: lib_misc.c + * + * Miscellaneous library routines. + * + * Author: Mitch Lichtenberg (mpl@broadcom.com) + * + ********************************************************************* + * + * Copyright 2000,2001,2002,2003 + * Broadcom Corporation. All rights reserved. + * + * This software is furnished under license and may be used and + * copied only in accordance with the following terms and + * conditions. Subject to these conditions, you may download, + * copy, install, use, modify and distribute modified or unmodified + * copies of this software in source and/or binary form. No title + * or ownership is transferred hereby. + * + * 1) Any source code used, modified or distributed must reproduce + * and retain this copyright notice and list of conditions + * as they appear in the source file. + * + * 2) No right is granted to use any trade name, trademark, or + * logo of Broadcom Corporation. The "Broadcom Corporation" + * name may not be used to endorse or promote products derived + * from this software without the prior written permission of + * Broadcom Corporation. + * + * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED + * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR + * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT + * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN + * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR 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), EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************* */ + + +#include "lib_types.h" +#include "lib_malloc.h" +#define _LIB_NO_MACROS_ +#include "lib_string.h" + + +/* ********************************************************************* + * lib_parseipaddr(ipaddr,dest) + * + * Parse an IP address. + * + * Input parameters: + * ipaddr - string of IP address + * dest - pointer to 4 bytes to receive binary IP address + * + * Return value: + * 0 if ok + * -1 if ip address is invalid + ********************************************************************* */ + +int lib_parseipaddr(const char *ipaddr,uint8_t *dest) +{ + int a,b,c,d; + char *x; + + /* make sure it's all digits and dots. */ + x = (char *) ipaddr; + while (*x) { + if ((*x == '.') || ((*x >= '0') && (*x <= '9'))) { + x++; + continue; + } + return -1; + } + + x = (char *) ipaddr; + a = lib_atoi(ipaddr); + x = lib_strchr(x,'.'); + if (!x) return -1; + b = lib_atoi(x+1); + x = lib_strchr(x+1,'.'); + if (!x) return -1; + c = lib_atoi(x+1); + x = lib_strchr(x+1,'.'); + if (!x) return -1; + d = lib_atoi(x+1); + + if ((a < 0) || (a > 255)) return -1; + if ((b < 0) || (b > 255)) return -1; + if ((c < 0) || (c > 255)) return -1; + if ((d < 0) || (d > 255)) return -1; + + dest[0] = (uint8_t) a; + dest[1] = (uint8_t) b; + dest[2] = (uint8_t) c; + dest[3] = (uint8_t) d; + + return 0; +} + + +/* ********************************************************************* + * lib_lookup(list,str) + * + * Look up an element on a {string,value} list. + * + * Input parameters: + * list - list to search + * str - string to find on the list + * + * Return value: + * 0 if string was not found + * else number associated with this string + ********************************************************************* */ + +int lib_lookup(const cons_t *list,char *str) +{ + while (list->str) { + if (lib_strcmp(list->str,str) == 0) return list->num; + list++; + } + + return 0; + +} + +/* ********************************************************************* + * lib_findinlist(list,str) + * + * Like lib_lookup but returns cons structure instead of value + * + * Input parameters: + * list - list of associations + * str - what to find + * + * Return value: + * cons_t or null if not found + ********************************************************************* */ + +static const cons_t *lib_findinlist(const cons_t *list,char *str) +{ + while (list->str) { + if (lib_strcmp(list->str,str) == 0) return list; + list++; + } + return NULL; +} + + +/* ********************************************************************* + * lib_setoptions(list,str,flags) + * + * Set or reset one or more bits in a flags variable based + * on the list of valid bits and a string containing what + * to change. flags starts off as a default value. + * + * The input string is a comma-separated list of options, + * optionally prefixed by "no_" or "no" to invert the + * sense of the option. negative values in the table + * remove options, positive add options (you can't use + * bit 31 as an option for this reason). + * + * Input parameters: + * list - list of valid options + * str - options to parse + * flags - pointer to variable to be modified + * + * Return value: + * number of options we did not understand, 0=ok + ********************************************************************* */ + +int lib_setoptions(const cons_t *list,char *str,unsigned int *flags) +{ + char *dupstr; + char *x; + char *ptr; + const cons_t *val; + int newbits; + int errors = 0; + + if (!list || !str || !flags) return 0; + + dupstr = lib_strdup(str); + if (!dupstr) return 0; + + ptr = dupstr; + + while (*ptr) { + if ((x = lib_strchr(ptr,','))) { + *x = '\0'; + } + + val = lib_findinlist(list,ptr); + newbits = 0; + if (!val) { + if (lib_memcmp(ptr,"no_",3) == 0) { + val = lib_findinlist(list,ptr+3); + } + else if (lib_memcmp(ptr,"no",2) == 0) { + val = lib_findinlist(list,ptr+2); + } + if (val) newbits = ~((unsigned int) (val->num)); + else errors++; + } + else { + newbits = (val->num); + } + + /* if new bits are negative, it's an AND mask + otherwise it's an OR mask */ + + if (newbits < 0) *flags &= (unsigned int) newbits; + else *flags |= (unsigned int) newbits; + + if (x) ptr = x+1; + else break; + } + + KFREE(dupstr); + + return errors; +} diff --git a/cfe/cfe/lib/lib_printf.c b/cfe/cfe/lib/lib_printf.c new file mode 100644 index 0000000..7dc3442 --- /dev/null +++ b/cfe/cfe/lib/lib_printf.c @@ -0,0 +1,442 @@ +/* ********************************************************************* + * Broadcom Common Firmware Environment (CFE) + * + * simple printf File: lib_printf.c + * + * Author: Mitch Lichtenberg (mpl@broadcom.com) + * + * This module contains a very, very, very simple printf + * suitable for use in the boot ROM. + * + ********************************************************************* + * + * Copyright 2000,2001,2002,2003 + * Broadcom Corporation. All rights reserved. + * + * This software is furnished under license and may be used and + * copied only in accordance with the following terms and + * conditions. Subject to these conditions, you may download, + * copy, install, use, modify and distribute modified or unmodified + * copies of this software in source and/or binary form. No title + * or ownership is transferred hereby. + * + * 1) Any source code used, modified or distributed must reproduce + * and retain this copyright notice and list of conditions + * as they appear in the source file. + * + * 2) No right is granted to use any trade name, trademark, or + * logo of Broadcom Corporation. The "Broadcom Corporation" + * name may not be used to endorse or promote products derived + * from this software without the prior written permission of + * Broadcom Corporation. + * + * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED + * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR + * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT + * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN + * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR 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), EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************* */ + +#include <stdarg.h> +#include "lib_types.h" +#include "lib_printf.h" + +/* ********************************************************************* + * Externs * + ********************************************************************* */ + +/* ********************************************************************* + * Globals * + ********************************************************************* */ + +static const char digits[17] = "0123456789ABCDEF"; +static const char ldigits[17] = "0123456789abcdef"; + +int (*xprinthook)(const char *str) = NULL; + +/* ********************************************************************* + * __atox(buf,num,radix,width) + * + * Convert a number to a string + * + * Input Parameters: + * buf - where to put characters + * num - number to convert + * radix - radix to convert number to (usually 10 or 16) + * width - width in characters + * + * Return Value: + * number of digits placed in output buffer + ********************************************************************* */ +static int __atox(char *buf,unsigned int num,unsigned int radix,int width, + const char *digits) +{ + char buffer[16]; + char *op; + int retval; + + op = &buffer[0]; + retval = 0; + + do { + *op++ = digits[num % radix]; + retval++; + num /= radix; + } while (num != 0); + + if (width && (width > retval)) { + width = width - retval; + while (width) { + *op++ = '0'; + retval++; + width--; + } + } + + while (op != buffer) { + op--; + *buf++ = *op; + } + + return retval; +} + + +/* ********************************************************************* + * __llatox(buf,num,radix,width) + * + * Convert a long number to a string + * + * Input Parameters: + * buf - where to put characters + * num - number to convert + * radix - radix to convert number to (usually 10 or 16) + * width - width in characters + * + * Return Value: + * number of digits placed in output buffer + ********************************************************************* */ +static int __llatox(char *buf,unsigned long long num,unsigned int radix, + int width,const char *digits) +{ + char buffer[16]; + char *op; + int retval; + + op = &buffer[0]; + retval = 0; + +#ifdef _MIPSREGS32_ + /* + * Hack: to avoid pulling in the helper library that isn't necessarily + * compatible with PIC code, force radix to 16, use shifts and masks + */ + do { + *op++ = digits[num & 0x0F]; + retval++; + num >>= 4; + } while (num != 0); +#else + do { + *op++ = digits[num % radix]; + retval++; + num /= radix; + } while (num != 0); +#endif + + if (width && (width > retval)) { + width = width - retval; + while (width) { + *op++ = '0'; + retval++; + width--; + } + } + + while (op != buffer) { + op--; + *buf++ = *op; + } + + return retval; +} + +/* ********************************************************************* + * xvsprintf(outbuf,template,arglist) + * + * Format a string into the output buffer + * + * Input Parameters: + * outbuf - output buffer + * template - template string + * arglist - parameters + * + * Return Value: + * number of characters copied + ********************************************************************* */ +#define isdigit(x) (((x) >= '0') && ((x) <= '9')) +int xvsprintf(char *outbuf,const char *templat,va_list marker) +{ + char *optr; + const char *iptr; + unsigned char *tmpptr; + unsigned int x; + unsigned long long lx; + int i; + long long ll; + int leadingzero; + int leadingnegsign; + int islong; + int width; + int width2 = 0; + int hashash = 0; + + optr = outbuf; + iptr = templat; + + while (*iptr) { + if (*iptr != '%') {*optr++ = *iptr++; continue;} + + iptr++; + + if (*iptr == '#') { hashash = 1; iptr++; } + if (*iptr == '-') { + leadingnegsign = 1; + iptr++; + } + else leadingnegsign = 0; + + if (*iptr == '0') leadingzero = 1; + else leadingzero = 0; + + width = 0; + while (*iptr && isdigit(*iptr)) { + width += (*iptr - '0'); + iptr++; + if (isdigit(*iptr)) width *= 10; + } + if (*iptr == '.') { + iptr++; + width2 = 0; + while (*iptr && isdigit(*iptr)) { + width2 += (*iptr - '0'); + iptr++; + if (isdigit(*iptr)) width2 *= 10; + } + } + + islong = 0; + if (*iptr == 'l') { islong++; iptr++; } + if (*iptr == 'l') { islong++; iptr++; } + + switch (*iptr) { + case 'I': + tmpptr = (unsigned char *) va_arg(marker,unsigned char *); + optr += __atox(optr,*tmpptr++,10,0,digits); + *optr++ = '.'; + optr += __atox(optr,*tmpptr++,10,0,digits); + *optr++ = '.'; + optr += __atox(optr,*tmpptr++,10,0,digits); + *optr++ = '.'; + optr += __atox(optr,*tmpptr++,10,0,digits); + break; + case 's': + tmpptr = (unsigned char *) va_arg(marker,unsigned char *); + if (!tmpptr) tmpptr = (unsigned char *) "(null)"; + if ((width == 0) & (width2 == 0)) { + while (*tmpptr) *optr++ = *tmpptr++; + break; + } + while (width && *tmpptr) { + *optr++ = *tmpptr++; + width--; + } + while (width) { + *optr++ = ' '; + width--; + } + break; + case 'a': + tmpptr = (unsigned char *) va_arg(marker,unsigned char *); + for (x = 0; x < 5; x++) { + optr += __atox(optr,*tmpptr++,16,2,digits); + *optr++ = '-'; + } + optr += __atox(optr,*tmpptr++,16,2,digits); + break; + case 'd': + switch (islong) { + case 0: + case 1: + i = va_arg(marker,int); + if (i < 0) { *optr++='-'; i = -i;} + optr += __atox(optr,i,10,width,digits); + break; + case 2: + ll = va_arg(marker,long long int); + if (ll < 0) { *optr++='-'; ll = -ll;} + optr += __llatox(optr,ll,10,width,digits); + break; + } + break; + case 'u': + switch (islong) { + case 0: + case 1: + x = va_arg(marker,unsigned int); + optr += __atox(optr,x,10,width,digits); + break; + case 2: + lx = va_arg(marker,unsigned long long); + optr += __llatox(optr,lx,10,width,digits); + break; + } + break; + case 'X': + case 'x': + switch (islong) { + case 0: + case 1: + x = va_arg(marker,unsigned int); + optr += __atox(optr,x,16,width, + (*iptr == 'X') ? digits : ldigits); + break; + case 2: + lx = va_arg(marker,unsigned long long); + optr += __llatox(optr,lx,16,width, + (*iptr == 'X') ? digits : ldigits); + break; + } + break; + case 'p': + case 'P': +#ifdef __long64 + lx = va_arg(marker,unsigned long long); + optr += __llatox(optr,lx,16,16, + (*iptr == 'P') ? digits : ldigits); +#else + x = va_arg(marker,unsigned int); + optr += __atox(optr,x,16,8, + (*iptr == 'P') ? digits : ldigits); +#endif + break; + case 'w': + x = va_arg(marker,unsigned int); + x &= 0x0000FFFF; + optr += __atox(optr,x,16,4,digits); + break; + case 'b': + x = va_arg(marker,unsigned int); + x &= 0x0000FF; + optr += __atox(optr,x,16,2,digits); + break; + case 'Z': + x = va_arg(marker,unsigned int); + tmpptr = va_arg(marker,unsigned char *); + while (x) { + optr += __atox(optr,*tmpptr++,16,2,digits); + x--; + } + break; + case 'c': + x = va_arg(marker, int); + *optr++ = x & 0xff; + break; + + default: + *optr++ = *iptr; + break; + } + iptr++; + } + + *optr = '\0'; + + return (optr - outbuf); +} + + +/* ********************************************************************* + * xsprintf(buf,template,params..) + * + * format messages from template into a buffer. + * + * Input Parameters: + * buf - output buffer + * template - template string + * params... parameters + * + * Return Value: + * number of bytes copied to buffer + ********************************************************************* */ +int xsprintf(char *buf,const char *templat,...) +{ + va_list marker; + int count; + + va_start(marker,templat); + count = xvsprintf(buf,templat,marker); + va_end(marker); + + return count; +} + +/* ********************************************************************* + * xprintf(template,...) + * + * A miniature printf. + * + * %a - Ethernet address (16 bytes) + * %s - unpacked string, null terminated + * %x - hex word (machine size) + * %w - hex word (16 bits) + * %b - hex byte (8 bits) + * %Z - buffer (put length first, then buffer address) + * + * Return value: + * number of bytes written + ********************************************************************* */ + +int xprintf(const char *templat,...) +{ + va_list marker; + int count; + char buffer[512]; + + va_start(marker,templat); + count = xvsprintf(buffer,templat,marker); + va_end(marker); + + if (xprinthook) (*xprinthook)(buffer); + + return count; +} + + +int xvprintf(const char *templat,va_list marker) +{ + int count; + char buffer[512]; + + count = xvsprintf(buffer,templat,marker); + + if (xprinthook) (*xprinthook)(buffer); + + return count; +} + + + + + + + + diff --git a/cfe/cfe/lib/lib_qsort.c b/cfe/cfe/lib/lib_qsort.c new file mode 100644 index 0000000..f3c60b8 --- /dev/null +++ b/cfe/cfe/lib/lib_qsort.c @@ -0,0 +1,88 @@ +#include "lib_types.h" +#include "lib_string.h" + +#define CHAR_BIT 8 +#define MAXSTACK (sizeof(int) * CHAR_BIT) + +static void qsexchange(void *a, void *b, size_t size) +{ + size_t i; + + /****************** + * exchange a,b * + ******************/ + + for (i = sizeof(int); i <= size; i += sizeof(int)) { + int t = *((int *)a); + *(((int *)a)++) = *((int *)b); + *(((int *)b)++) = t; + } + for (i = i - sizeof(int) + 1; i <= size; i++) { + char t = *((char *)a); + *(((char *)a)++) = *((char *)b); + *(((char *)b)++) = t; + } +} + +void qsort(void *base, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) +{ + void *lbStack[MAXSTACK], *ubStack[MAXSTACK]; + int sp; + unsigned int offset; + + /******************** + * ANSI-C qsort() * + ********************/ + + lbStack[0] = (char *)base; + ubStack[0] = (char *)base + (nmemb-1)*size; + for (sp = 0; sp >= 0; sp--) { + char *lb, *ub, *m; + char *P, *i, *j; + + lb = lbStack[sp]; + ub = ubStack[sp]; + + while (lb < ub) { + + /* select pivot and exchange with 1st element */ + offset = (ub - lb) >> 1; + P = lb + offset - offset % size; + qsexchange (lb, P, size); + + /* partition into two segments */ + i = lb + size; + j = ub; + while (1) { + while (i < j && compar(lb, i) > 0) i += size; + while (j >= i && compar(j, lb) > 0) j -= size; + if (i >= j) break; + qsexchange (i, j, size); + j -= size; + i += size; + } + + /* pivot belongs in A[j] */ + qsexchange (lb, j, size); + m = j; + + /* keep processing smallest segment, and stack largest */ + if (m - lb <= ub - m) { + if (m + size < ub) { + lbStack[sp] = m + size; + ubStack[sp++] = ub; + } + ub = m - size; + } + else { + if (m - size > lb) { + lbStack[sp] = lb; + ubStack[sp++] = m - size; + } + lb = m + size; + } + } + } +} + diff --git a/cfe/cfe/lib/lib_queue.c b/cfe/cfe/lib/lib_queue.c new file mode 100644 index 0000000..0712adf --- /dev/null +++ b/cfe/cfe/lib/lib_queue.c @@ -0,0 +1,219 @@ +/* ********************************************************************* + * Broadcom Common Firmware Environment (CFE) + * + * Queue Management routines File: lib_queue.c + * + * Routines to manage doubly-linked queues. + * + * Author: Mitch Lichtenberg (mpl@broadcom.com) + * + ********************************************************************* + * + * Copyright 2000,2001,2002,2003 + * Broadcom Corporation. All rights reserved. + * + * This software is furnished under license and may be used and + * copied only in accordance with the following terms and + * conditions. Subject to these conditions, you may download, + * copy, install, use, modify and distribute modified or unmodified + * copies of this software in source and/or binary form. No title + * or ownership is transferred hereby. + * + * 1) Any source code used, modified or distributed must reproduce + * and retain this copyright notice and list of conditions + * as they appear in the source file. + * + * 2) No right is granted to use any trade name, trademark, or + * logo of Broadcom Corporation. The "Broadcom Corporation" + * name may not be used to endorse or promote products derived + * from this software without the prior written permission of + * Broadcom Corporation. + * + * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED + * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR + * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT + * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN + * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR 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), EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************* */ + + +#include "lib_types.h" +#include "lib_queue.h" + + +/* ********************************************************************* + * Q_ENQUEUE(qb,item) + * + * Add item to a queue + * + * Input Parameters: + * qb - queue block + * item - item to add + * + * Return Value: + * Nothing. + ********************************************************************* */ + +void q_enqueue(queue_t *qb,queue_t *item) +{ + qb->q_prev->q_next = item; + item->q_next = qb; + item->q_prev = qb->q_prev; + qb->q_prev = item; +} + + +/* ********************************************************************* + * Q_DEQUEUE(element) + * + * Remove an element from the queue + * + * Input Parameters: + * element - element to remove + * + * Return Value: + * Nothing. + ********************************************************************* */ + +void q_dequeue(queue_t *item) +{ + item->q_prev->q_next = item->q_next; + item->q_next->q_prev = item->q_prev; +} + + +/* ********************************************************************* + * Q_DEQNEXT(qb) + * + * Dequeue next element from the specified queue + * + * Input Parameters: + * qb - queue block + * + * Return Value: + * next element, or NULL + ********************************************************************* */ + +queue_t *q_deqnext(queue_t *qb) +{ + if (qb->q_next == qb) { + return NULL; + } + + qb = qb->q_next; + + qb->q_prev->q_next = qb->q_next; + qb->q_next->q_prev = qb->q_prev; + + return qb; +} + + +/* ********************************************************************* + * Q_MAP(qb) + * + * "Map" a queue, calling the specified function for each + * element in the queue + * + * If the function returns nonzero, q_map will terminate. + * + * Input Parameters: + * qb - queue block + * fn - function pointer + * a,b - parameters for the function + * + * Return Value: + * return value from function, or zero if entire queue + * was mapped. + ********************************************************************* */ + +int q_map(queue_t *qb, int (*func)(queue_t *,unsigned int,unsigned int), + unsigned int a,unsigned int b) +{ + queue_t *qe; + queue_t *nextq; + int res; + + qe = qb; + + qe = qb->q_next; + + while (qe != qb) { + nextq = qe->q_next; + if ((res = (*func)(qe,a,b))) return res; + qe = nextq; + } + + return 0; +} + + + + + +/* ********************************************************************* + * Q_COUNT(qb) * + * * + * Counts the elements on a queue (not interlocked) * + * * + * Input Parameters: * + * qb - queue block * + * * + * Return Value: * + * number of elements * + ********************************************************************* */ +int q_count(queue_t *qb) +{ + queue_t *qe; + int res = 0; + + qe = qb; + + while (qe->q_next != qb) { + qe = qe->q_next; + res++; + } + + return res; +} + + + + +/* ********************************************************************* + * Q_FIND(qb,item) + * + * Determines if a particular element is on a queue. + * + * Input Parameters: + * qb - queue block + * item - queue element + * + * Return Value: + * 0 - not on queue + * >0 - position on queue + ********************************************************************* */ +int q_find(queue_t *qb,queue_t *item) +{ + queue_t *q; + int res = 1; + + q = qb->q_next; + + while (q != item) { + if (q == qb) return 0; + q = q->q_next; + res++; + } + + return res; +} + diff --git a/cfe/cfe/lib/lib_string.c b/cfe/cfe/lib/lib_string.c new file mode 100644 index 0000000..08e9ee7 --- /dev/null +++ b/cfe/cfe/lib/lib_string.c @@ -0,0 +1,386 @@ +/* ********************************************************************* + * Broadcom Common Firmware Environment (CFE) + * + * String routines File: lib_string.c + * + * Some standard routines for messing with strings. + * + * Author: Mitch Lichtenberg (mpl@broadcom.com) + * + ********************************************************************* + * + * Copyright 2000,2001,2002,2003 + * Broadcom Corporation. All rights reserved. + * + * This software is furnished under license and may be used and + * copied only in accordance with the following terms and + * conditions. Subject to these conditions, you may download, + * copy, install, use, modify and distribute modified or unmodified + * copies of this software in source and/or binary form. No title + * or ownership is transferred hereby. + * + * 1) Any source code used, modified or distributed must reproduce + * and retain this copyright notice and list of conditions + * as they appear in the source file. + * + * 2) No right is granted to use any trade name, trademark, or + * logo of Broadcom Corporation. The "Broadcom Corporation" + * name may not be used to endorse or promote products derived + * from this software without the prior written permission of + * Broadcom Corporation. + * + * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED + * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR + * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT + * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN + * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR 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), EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************* */ + + + + +#include "lib_types.h" +#define _LIB_NO_MACROS_ +#include "lib_string.h" + +char *lib_strcpy(char *dest,const char *src) +{ + char *ptr = dest; + + while (*src) *ptr++ = *src++; + *ptr = '\0'; + + return dest; +} + +char *lib_strncpy(char *dest,const char *src,size_t cnt) +{ + char *ptr = dest; + + while (*src && (cnt > 0)) { + *ptr++ = *src++; + cnt--; + } + if (cnt > 0) *ptr = '\0'; + + return dest; +} + + +size_t lib_xstrncpy(char *dest,const char *src,size_t cnt) +{ + char *ptr = dest; + size_t copied = 0; + + while (*src && (cnt > 1)) { + *ptr++ = *src++; + cnt--; + copied++; + } + *ptr = '\0'; + + return copied; +} + +size_t lib_strlen(const char *str) +{ + size_t cnt = 0; + + while (*str) { + str++; + cnt++; + } + + return cnt; +} + + +int lib_strcmp(const char *dest,const char *src) +{ + while (*src && *dest) { + if (*dest < *src) return -1; + if (*dest > *src) return 1; + dest++; + src++; + } + + if (*dest && !*src) return 1; + if (!*dest && *src) return -1; + return 0; +} + +/* Foxconn add start by Jenny Zhao, 07/02/2008*/ +int lib_strncmp(const char *dest, const char *src, size_t cnt ) +{ + while (*src && *dest && cnt) { + if (*dest < *src ) return -1; + if (*dest > *src) return 1; + dest++; + src++; + cnt--; + } + + if (!cnt) return 0; + if (*dest && !*src) return 1; + if (!*dest && *src) return -1; + return 0; +} +/* Foxconn add start by Jenny Zhao, 07/02/2008*/ + + +int lib_strcmpi(const char *dest,const char *src) +{ + char dc,sc; + + while (*src && *dest) { + dc = lib_toupper(*dest); + sc = lib_toupper(*src); + if (dc < sc) return -1; + if (dc > sc) return 1; + dest++; + src++; + } + + if (*dest && !*src) return 1; + if (!*dest && *src) return -1; + return 0; +} + + +char *lib_strchr(const char *dest,int c) +{ + while (*dest) { + if (*dest == c) return (char *) dest; + dest++; + } + return NULL; +} + +char *lib_strnchr(const char *dest,int c,size_t cnt) +{ + while (*dest && (cnt > 0)) { + if (*dest == c) return (char *) dest; + dest++; + cnt--; + } + return NULL; +} + +char *lib_strrchr(const char *dest,int c) +{ + char *ret = NULL; + + while (*dest) { + if (*dest == c) ret = (char *) dest; + dest++; + } + + return ret; +} + + +int lib_memcmp(const void *dest,const void *src,size_t cnt) +{ + const unsigned char *d; + const unsigned char *s; + + d = (const unsigned char *) dest; + s = (const unsigned char *) src; + + while (cnt) { + if (*d < *s) return -1; + if (*d > *s) return 1; + d++; s++; cnt--; + } + + return 0; +} + +void *lib_memcpy(void *dest,const void *src,size_t cnt) +{ + unsigned char *d; + const unsigned char *s; + + d = (unsigned char *) dest; + s = (const unsigned char *) src; + + while (cnt) { + *d++ = *s++; + cnt--; + } + + return dest; +} + +void *lib_memset(void *dest,int c,size_t cnt) +{ + unsigned char *d; + + d = dest; + + while (cnt) { + *d++ = (unsigned char) c; + cnt--; + } + + return d; +} + +char lib_toupper(char c) +{ + if ((c >= 'a') && (c <= 'z')) c -= 32; + return c; +} + +void lib_strupr(char *str) +{ + while (*str) { + *str = lib_toupper(*str); + str++; + } +} + +char *lib_strcat(char *dest,const char *src) +{ + char *ptr = dest; + + while (*ptr) ptr++; + while (*src) *ptr++ = *src++; + *ptr = '\0'; + + return dest; +} + +#define isspace(x) (((x) == ' ') || ((x) == '\t')) + +char *lib_gettoken(char **ptr) +{ + char *p = *ptr; + char *ret; + + /* skip white space */ + + while (*p && isspace(*p)) p++; + ret = p; + + /* check for end of string */ + + if (!*p) { + *ptr = p; + return NULL; + } + + /* skip non-whitespace */ + + while (*p) { + if (isspace(*p)) break; + + /* do quoted strings */ + + if (*p == '"') { + p++; + ret = p; + while (*p && (*p != '"')) p++; + if (*p == '"') *p = '\0'; + } + + p++; + + } + + if (*p) { + *p++ = '\0'; + } + *ptr = p; + + return ret; +} + + +int lib_atoi(const char *dest) +{ + int x = 0; + int digit; + + if ((*dest == '0') && (*(dest+1) == 'x')) { + return lib_xtoi(dest+2); + } + + while (*dest) { + if ((*dest >= '0') && (*dest <= '9')) { + digit = *dest - '0'; + } + else { + break; + } + x *= 10; + x += digit; + dest++; + } + + return x; +} + +uint64_t lib_xtoq(const char *dest) +{ + uint64_t x = 0; + unsigned int digit; + + if ((*dest == '0') && (*(dest+1) == 'x')) dest += 2; + + while (*dest) { + if ((*dest >= '0') && (*dest <= '9')) { + digit = *dest - '0'; + } + else if ((*dest >= 'A') && (*dest <= 'F')) { + digit = 10 + *dest - 'A'; + } + else if ((*dest >= 'a') && (*dest <= 'f')) { + digit = 10 + *dest - 'a'; + } + else { + break; + } + x *= 16; + x += digit; + dest++; + } + + return x; +} + +int lib_xtoi(const char *dest) +{ + int x = 0; + int digit; + + if ((*dest == '0') && (*(dest+1) == 'x')) dest += 2; + + while (*dest) { + if ((*dest >= '0') && (*dest <= '9')) { + digit = *dest - '0'; + } + else if ((*dest >= 'A') && (*dest <= 'F')) { + digit = 10 + *dest - 'A'; + } + else if ((*dest >= 'a') && (*dest <= 'f')) { + digit = 10 + *dest - 'a'; + } + else { + break; + } + x *= 16; + x += digit; + dest++; + } + + return x; +} diff --git a/cfe/cfe/lib/lib_string2.c b/cfe/cfe/lib/lib_string2.c new file mode 100644 index 0000000..e42070a --- /dev/null +++ b/cfe/cfe/lib/lib_string2.c @@ -0,0 +1,96 @@ +/* ********************************************************************* + * Broadcom Common Firmware Environment (CFE) + * + * More string routines File: lib_string2.c + * + * More routines to muck with strings; these routines typically + * need malloc to operate. This way lib_string.c can be incorporated + * into other programs that don't need malloc + * + * Author: Mitch Lichtenberg (mpl@broadcom.com) + * + ********************************************************************* + * + * Copyright 2000,2001,2002,2003 + * Broadcom Corporation. All rights reserved. + * + * This software is furnished under license and may be used and + * copied only in accordance with the following terms and + * conditions. Subject to these conditions, you may download, + * copy, install, use, modify and distribute modified or unmodified + * copies of this software in source and/or binary form. No title + * or ownership is transferred hereby. + * + * 1) Any source code used, modified or distributed must reproduce + * and retain this copyright notice and list of conditions + * as they appear in the source file. + * + * 2) No right is granted to use any trade name, trademark, or + * logo of Broadcom Corporation. The "Broadcom Corporation" + * name may not be used to endorse or promote products derived + * from this software without the prior written permission of + * Broadcom Corporation. + * + * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED + * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR + * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT + * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN + * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR 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), EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************* */ + + + +#include "lib_types.h" +#include "lib_malloc.h" +#define _LIB_NO_MACROS_ +#include "lib_string.h" + + +char *lib_strdup(char *str) +{ + char *buf; + + buf = KMALLOC(lib_strlen(str)+1,0); + if (buf) { + lib_strcpy(buf,str); + } + + return buf; +} + +void lib_trimleading(char *path) +{ + if (*path == '/') { + lib_strcpy(path, path+1); + } + + return; +} + +void lib_chop_filename(char *str,char **host,char **file) +{ + char *p; + + *host = str; + + p = lib_strchr(str,':'); + if (!p) p = lib_strchr(str,'/'); + + if (p) { + *p++ = '\0'; + *file = p; + } + else { + *file = NULL; + } +} + + |