From 0256fdf30b44395d9695a5306d8b1d5485e602db Mon Sep 17 00:00:00 2001 From: Alan Korr Date: Wed, 17 Apr 2002 12:20:41 +0000 Subject: cosmetic changes and additions : * now we have seperate private headers files containing private and static or public functions in memory-* files. * there is only one .c file of the same name the library. Zagor: because now there is only one .c file, you could only have a .o file and use it instead of the .a libfile. * most structures and codes are now private. git-svn-id: svn://svn.rockbox.org/rockbox/trunk@113 a1c6a512-1295-4272-9138-f99709370657 --- firmware/test/memory/memory-page.h | 425 +++++++++++++++++++++++++++++++++++++ 1 file changed, 425 insertions(+) create mode 100644 firmware/test/memory/memory-page.h (limited to 'firmware/test/memory/memory-page.h') diff --git a/firmware/test/memory/memory-page.h b/firmware/test/memory/memory-page.h new file mode 100644 index 0000000000..438fd63669 --- /dev/null +++ b/firmware/test/memory/memory-page.h @@ -0,0 +1,425 @@ +/*************************************************************************** + * __________ __ ___. + * Open \______ \ ____ ____ | | _\_ |__ _______ ___ + * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / + * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < + * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ + * \/ \/ \/ \/ \/ + * $Id: + * + * Copyright (C) 2002 by Alan Korr + * + * All files in this archive are subject to the GNU General Public License. + * See the file COPYING in the source tree root for full license agreement. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + ****************************************************************************/ +#ifndef __LIBRARY_MEMORY_C__ +# error "This header file must be included ONLY from memory.c." +#endif +#ifndef __LIBRARY_MEMORY_PAGE_H__ +# define __LIBRARY_MEMORY_PAGE_H__ + +struct memory_free_page + { + struct memory_free_page + *less,*more; + char + reserved[MEMORY_PAGE_MINIMAL_SIZE - 2*sizeof (struct memory_free_page *)]; + }; + +#define LESS -1 +#define MORE +1 + +#ifdef TEST + +struct memory_free_page free_page[MEMORY_TOTAL_PAGES]; + +static inline unsigned int get_offset (int order) + { + return (2 << order); + } + +// IA32 has no problem with shift operation +static inline unsigned int get_size (int order) + { + return (MEMORY_PAGE_MINIMAL_SIZE << order); + } + +// Arghhhh ! I cannot align 'free_page' on 512-byte boundary (max is 16-byte for Cygwin) +static inline struct memory_free_page *get_neighbour (struct memory_free_page *node,unsigned int size) + { + return ((struct memory_free_page *)((unsigned)free_page + (((unsigned)node - (unsigned)free_page) ^ size))); + } + +#else + +extern struct memory_free_page free_page[MEMORY_TOTAL_PAGES] asm("dram"); + +static inline unsigned int get_offset (int order) + { + static unsigned short offset [MEMORY_TOTAL_ORDERS] = + { 2,4,8,16,32,64,128,256,512,1024,2048,4096,8192 }; + return offset[order]; + } + +// SH1 has very poor shift instructions (only <<1,>>1,<<2,>>2,<<8,>>8,<<16 and >>16). +// so we should use a lookup table to speedup. +static inline unsigned int get_size (int order) + { + return (get_offset (order))<<8; + } + +static inline struct memory_free_page *get_neighbour (struct memory_free_page *node,unsigned int size) + { + return ((struct memory_free_page *)((unsigned)node ^ size)); + } + +#endif + +static char free_page_order[MEMORY_TOTAL_PAGES]; +static struct memory_free_page *free_page_bin[MEMORY_TOTAL_ORDERS]; + +static inline int get_order (struct memory_free_page *node) + { + return free_page_order[node - free_page]; + } +static inline void set_order (struct memory_free_page *node,int order) + { + free_page_order[node - free_page] = order; + } + +#if MEMORY_PAGE_USE_SPLAY_TREE + +# include + +static struct memory_free_page *splay_page (struct memory_free_page *root,struct memory_free_page *node) + { + struct memory_free_page *down; + struct memory_free_page *less; + struct memory_free_page *more; + struct memory_free_page head; + head.less = + head.more = 0; + less = + more = &head; + while (1) + { + if (node < root) + { + if ((down = root->less)) + { + if (node < down) + { + root->less = down->more; + down->more = root; + root = down; + if (!root->less) + break; + } + more->less = root; + more = root; + root = root->less; + continue; + } + break; + } + if (root < node) + { + if ((down = root->more)) + { + if (root < node) + { + root->more = down->less; + down->less = root; + root = down; + if (!root->more) + break; + } + less->more = root; + less = root; + root = root->more; + continue; + } + } + break; + } + less->more = root->less; + more->less = root->more; + root->less = head.more; + root->more = head.less; + return root; + } + +static inline void insert_page (int order,struct memory_free_page *node) + { + struct memory_free_page *root = free_page_bin[order]; + if (!root) + { + node->less = + node->more = 0; + } + else if (node < (root = splay_page (root,node))) + { + node->less = root->less; + node->more = root; + root->less = 0; + } + else if (node > root) + { + node->less = root; + node->more = root->more; + node->more = 0; + } + free_page_bin[order] = node; + set_order (node,order); + return; + } + +static inline struct memory_free_page *pop_page (int order,int want) + { + struct memory_free_page *root = free_page_bin[order]; + if (root) + { + root = splay_page (root,free_page); + free_page_bin[order] = root->more; + set_order (root,~want); + } + return root; + } + +static inline void remove_page (int order,struct memory_free_page *node) + { + struct memory_free_page *root = free_page_bin[order]; + root = splay_page (root,node); + if (root->less) + { + node = splay_page (root->less,node); + node->more = root->more; + } + else + node = root->more; + free_page_bin[order] = node; + } + +#else + +static inline void insert_page (int order,struct memory_free_page *node) + { + struct memory_free_page *head = free_page_bin[order]; + node->less = 0; + node->more = head; + if (head) + head->less = node; + free_page_bin[order] = node; + set_order (node,order); + } + +static inline struct memory_free_page *pop_page (int order,int want) + { + struct memory_free_page *node = free_page_bin[order]; + if (node) + { + free_page_bin[order] = node->more; + if (node->more) + node->more->less = 0; + set_order (node,~want); + } + return node; + } + +static inline void remove_page (int order,struct memory_free_page *node) + { + if (node->less) + node->less->more = node->more; + else + free_page_bin[order] = node->more; + if (node->more) + node->more->less = node->less; + } + +#endif + +static inline void push_page (int order,struct memory_free_page *node) + { + node->less = 0; + node->more = 0; + free_page_bin[order] = node; + set_order (node,order); + } + +static struct memory_free_page *allocate_page (unsigned int size,int order) + { + struct memory_free_page *node; + int min = order; + while ((unsigned)order <= (MEMORY_TOTAL_ORDERS - 1)) + // order is valid ? + { + if (!(node = pop_page (order,min))) + // no free page of this order ? + { + ++order; size <<= 1; + continue; + } + while (order > min) + // split our larger page in smaller pages + { + --order; size >>= 1; + push_page (order,(struct memory_free_page *)((unsigned int)node + size)); + } + return node; + } + return MEMORY_RETURN_FAILURE; + } + +static inline void release_page (struct memory_free_page *node,unsigned int size,int order) + { + struct memory_free_page *neighbour; + while ((order <= (MEMORY_TOTAL_ORDERS - 1)) && + ((neighbour = get_neighbour (node,size)), + (get_order (neighbour) == order))) + // merge our released page with its contiguous page into a larger page + { + remove_page (order,neighbour); + ++order; size <<= 1; + if (neighbour < node) + node = neighbour; + } + insert_page (order,node); + } + + +/*****************************************************************************/ +/* PUBLIC FUNCTIONS */ +/*****************************************************************************/ + +void *memory_allocate_page (int order) + { + if (order < 0) + return MEMORY_RETURN_FAILURE; + return allocate_page (get_size (order),order); + } + +// release a page : +// when called, 'address' MUST be a valid address pointing +// to &dram[i], where i ranges from 0 to MEMORY_TOTAL_PAGES - 1. +// FAILURE if block is already freed. +int memory_release_page (void *address) + { + struct memory_free_page *node = (struct memory_free_page *)address; + int order = ~get_order (node); + if (order < 0) + return MEMORY_RETURN_FAILURE; + release_page (node,get_size (order),order); + return MEMORY_RETURN_SUCCESS; + } + + +#ifdef TEST +# include +# include +# if MEMORY_PAGE_USE_SPLAY_TREE + +static void dump_splay_node (struct memory_free_page *node,int level) + { + if (!node) + return; + dump_splay_node (node->less,level+1); + printf ("\n%*s[%d-%d]",level,"",(node - free_page),(node - free_page) + (1 << get_order (node)) - 1); + dump_splay_node (node->more,level+1); + } + +static void dump_splay_tree (struct memory_free_page *root) + { + dump_splay_node (root,2); fflush (stdout); + } + +# endif + +void memory_spy_page (void *address) + { + struct memory_free_page *node = (struct memory_free_page *)address; + int order,used; + if (node) + { + order = get_order (node); + used = order < 0; + if (used) + order = ~order; + printf("\n(%s,%2d,%7d)",(used ? "used" : "free"),order,get_size (order)); + } + } + +void memory_dump (int order) + { + struct memory_free_page *node = free_page_bin[order]; + printf("\n(%s,%2d,%7d)",node ? "free" : "none",order,get_size (order)); +# if MEMORY_PAGE_USE_SPLAY_TREE + dump_splay_tree (node); +# else + while (node) + { + printf("[%d-%d]",(node - free_page),(node - free_page) + (1<more; + } +# endif + + } + +void memory_check (int order) + { + struct memory_free_page *node[4096],*swap; + unsigned int i = 0,j = 0; + while (i <= 12) + memory_dump (i++); + i = 0; + printf ("\nallocating...\n"); + while (order >= 0) + { + j = order; + while ((swap = memory_allocate_page (j))) + { + node[i++] = swap; + printf("[%d-%d]",(swap - free_page),(swap - free_page) + ((1 << j)-1)); + for (j += (rand () & 15); j > (unsigned int)order; j -= order); + } + --order; + } + node[i] = 0; + while (j <= 12) + memory_dump (j++); + j = 0; + printf ("\nreleasing..."); + --i; + while (i > 0) + { + unsigned int k = 0; +#if 0 + printf ("\n"); +#endif + swap = node[k++]; +#if 0 + while (swap) + { + printf("[%d-%d]",(swap - free_page),(swap - free_page) + ((1 << ~get_order (swap))-1)); + swap = node[k++]; + } +#endif + for (j += 1 + (rand () & 15); j >= i; j -= i); + swap = node[j]; + node[j] = node[i]; + memory_release_page (swap); + node[i] = 0; + --i; + } + memory_release_page (node[0]); + i = 0; + while (i <= 12) + memory_dump (i++); + printf("\n\n%s !",(get_order (free_page) == 12) ? "SUCCESS" : "FAILURE"); + } + +#endif +#endif \ No newline at end of file -- cgit v1.2.3