diff options
author | Alan Korr <alkorr@rockbox.org> | 2002-04-15 23:19:10 +0000 |
---|---|---|
committer | Alan Korr <alkorr@rockbox.org> | 2002-04-15 23:19:10 +0000 |
commit | 27df7b0b96686771b9fafba33d0a97b4d77f6206 (patch) | |
tree | 638189ff3754910b98f4725167fe621c4c20436a /firmware/test | |
parent | f5747cf78a4506dca544fde5324fd020a988c73b (diff) | |
download | rockbox-27df7b0b96686771b9fafba33d0a97b4d77f6206.tar.gz rockbox-27df7b0b96686771b9fafba33d0a97b4d77f6206.zip |
*** empty log message ***
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@98 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'firmware/test')
-rw-r--r-- | firmware/test/memory/config.h | 27 | ||||
-rw-r--r-- | firmware/test/memory/defines.h | 39 | ||||
-rw-r--r-- | firmware/test/memory/functions.h | 34 | ||||
-rw-r--r-- | firmware/test/memory/inlines.h | 26 | ||||
-rw-r--r-- | firmware/test/memory/makefile | 193 | ||||
-rw-r--r-- | firmware/test/memory/memory-page.c | 434 | ||||
-rw-r--r-- | firmware/test/memory/memory-slab.c | 463 | ||||
-rw-r--r-- | firmware/test/memory/memory.h | 27 | ||||
-rw-r--r-- | firmware/test/memory/return_values.h | 31 | ||||
-rw-r--r-- | firmware/test/memory/test.l | 23 | ||||
-rw-r--r-- | firmware/test/memory/test.y | 182 | ||||
-rw-r--r-- | firmware/test/memory/types.h | 72 |
12 files changed, 1551 insertions, 0 deletions
diff --git a/firmware/test/memory/config.h b/firmware/test/memory/config.h new file mode 100644 index 0000000000..cb3b75f09b --- /dev/null +++ b/firmware/test/memory/config.h | |||
@@ -0,0 +1,27 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id: | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef __LIBRARY_MEMORY_H__ | ||
20 | # error "This header file must be included ONLY from memory.h." | ||
21 | #endif | ||
22 | #ifndef __LIBRARY_MEMORY_CONFIG_H__ | ||
23 | # define __LIBRARY_MEMORY_CONFIG_H__ | ||
24 | # define PACKAGE_NAME "memory" | ||
25 | # define PACKAGE_VERSION "0.1.0" | ||
26 | # define MEMORY_PAGE_USE_SPLAY_TREE 1 | ||
27 | #endif \ No newline at end of file | ||
diff --git a/firmware/test/memory/defines.h b/firmware/test/memory/defines.h new file mode 100644 index 0000000000..a6e48cc7e6 --- /dev/null +++ b/firmware/test/memory/defines.h | |||
@@ -0,0 +1,39 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id: | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef __LIBRARY_MEMORY_H__ | ||
20 | # error "This header file must be included ONLY from memory.h." | ||
21 | #endif | ||
22 | #ifndef __LIBRARY_MEMORY_DEFINES_H__ | ||
23 | # define __LIBRARY_MEMORY_DEFINES_H__ | ||
24 | # ifndef MEMORY_PAGE_MINIMAL_ORDER | ||
25 | # define MEMORY_PAGE_MINIMAL_ORDER (9) /* 512 bytes */ | ||
26 | # endif | ||
27 | # ifndef MEMORY_PAGE_MAXIMAL_ORDER | ||
28 | # define MEMORY_PAGE_MAXIMAL_ORDER (21) /* 2 Mbytes */ | ||
29 | # endif | ||
30 | # ifndef MEMORY_PAGE_MINIMAL_SIZE | ||
31 | # define MEMORY_PAGE_MINIMAL_SIZE (1 << MEMORY_PAGE_MINIMAL_ORDER) | ||
32 | # endif | ||
33 | # ifndef MEMORY_PAGE_MAXIMAL_SIZE | ||
34 | # define MEMORY_PAGE_MAXIMAL_SIZE (1 << MEMORY_PAGE_MAXIMAL_ORDER) | ||
35 | # endif | ||
36 | # define MEMORY_TOTAL_PAGES (MEMORY_PAGE_MAXIMAL_SIZE / MEMORY_PAGE_MINIMAL_SIZE) | ||
37 | # define MEMORY_TOTAL_BYTES (MEMORY_PAGE_MAXIMAL_SIZE) | ||
38 | # define MEMORY_TOTAL_ORDERS (1 + MEMORY_PAGE_MAXIMAL_ORDER - MEMORY_PAGE_MINIMAL_ORDER) | ||
39 | #endif \ No newline at end of file | ||
diff --git a/firmware/test/memory/functions.h b/firmware/test/memory/functions.h new file mode 100644 index 0000000000..e0f6aeac97 --- /dev/null +++ b/firmware/test/memory/functions.h | |||
@@ -0,0 +1,34 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef __LIBRARY_MEMORY_H__ | ||
20 | # error "This header file must be included ONLY from memory.h." | ||
21 | #endif | ||
22 | # ifndef __LIBRARY_MEMORY_FUNCTIONS_H__ | ||
23 | # define __LIBRARY_MEMORY_FUNCTIONS_H__ | ||
24 | extern void memory_copy (void *target,void const *source,unsigned int count); | ||
25 | extern void memory_set (void *target,int byte,unsigned int count); | ||
26 | extern int memory_release_page (void *); | ||
27 | extern void *memory_allocate_page (int); | ||
28 | extern void memory_setup (void); | ||
29 | # ifdef TEST | ||
30 | void memory_spy_page (void *address); | ||
31 | void memory_dump (int order); | ||
32 | void memory_check (int order); | ||
33 | # endif | ||
34 | #endif | ||
diff --git a/firmware/test/memory/inlines.h b/firmware/test/memory/inlines.h new file mode 100644 index 0000000000..dee78a6204 --- /dev/null +++ b/firmware/test/memory/inlines.h | |||
@@ -0,0 +1,26 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id: | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef __LIBRARY_MEMORY_H__ | ||
20 | # error "This header file must be included ONLY from memory.h." | ||
21 | #endif | ||
22 | # ifndef __LIBRARY_MEMORY_INLINES_H__ | ||
23 | #define __LIBRARY_MEMORY_INLINES_H__ | ||
24 | |||
25 | |||
26 | #endif \ No newline at end of file | ||
diff --git a/firmware/test/memory/makefile b/firmware/test/memory/makefile new file mode 100644 index 0000000000..2259cdfce7 --- /dev/null +++ b/firmware/test/memory/makefile | |||
@@ -0,0 +1,193 @@ | |||
1 | ############################################################################# | ||
2 | ## __________ __ ___. | ||
3 | ## Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | ## Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | ## Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | ## Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | ## \/ \/ \/ \/ \/ | ||
8 | ## Copyright Alan Korr, 2002. All rights reserved. | ||
9 | ## | ||
10 | ## Permission to use, copy, modify, and distribute this software for any | ||
11 | ## purpose is hereby granted without fee, provided that this copyright and | ||
12 | ## permissions notice appear in all copies and derivatives, and that no | ||
13 | ## charge may be made for the software and its documentation except to cover | ||
14 | ## cost of distribution. | ||
15 | ## | ||
16 | ## This software is provided "as is" without express or implied warranty. | ||
17 | ############################################################################# | ||
18 | ARCH = test | ||
19 | |||
20 | CC = gcc | ||
21 | AS = as | ||
22 | LD = ld | ||
23 | AR = ar | ||
24 | RL = ranlib | ||
25 | OC = objcopy | ||
26 | GZ = gzip -f | ||
27 | |||
28 | PREFIX = ~/rockbox/$(ARCH) | ||
29 | PACKAGE = memory | ||
30 | VERSION = 0.1 | ||
31 | DEFINES = -DTEST | ||
32 | |||
33 | #####################################################" | ||
34 | # Compiler flags : | ||
35 | |||
36 | CFLAGS = -g | ||
37 | #CFLAGS += -save-temps | ||
38 | CFLAGS += -Wall \ | ||
39 | -W \ | ||
40 | -Wshadow \ | ||
41 | -Wpointer-arith \ | ||
42 | -Waggregate-return \ | ||
43 | -Wstrict-prototypes \ | ||
44 | -Wredundant-decls \ | ||
45 | -Winline \ | ||
46 | -Wmissing-prototypes \ | ||
47 | -Werror \ | ||
48 | -Wsign-compare \ | ||
49 | -Wmissing-declarations \ | ||
50 | -Wmissing-noreturns \ | ||
51 | -Wnested-externs | ||
52 | CFLAGS += -pipe -O3 | ||
53 | CFLAGS += -fomit-frame-pointer \ | ||
54 | -fschedule-insns | ||
55 | CFLAGS += $(EXTRA_CFLAGS) | ||
56 | CFLAGS += $(DEFINES) | ||
57 | |||
58 | ####################################################################### | ||
59 | ## PLEASE CONSIDER THERE IS NOTHING TO CHANGE IN THE FOLLOWING LINES | ||
60 | ## SINCE THERE ARE COMMON FOR ALL LIBRARY | ||
61 | ## | ||
62 | |||
63 | .SUFFIXES : .o .c .s | ||
64 | |||
65 | INCLUDES = -I. \ | ||
66 | -I$(PREFIX)/headers | ||
67 | |||
68 | STATIC_LIBRARY_PATH = $(PREFIX)/libraries | ||
69 | |||
70 | LIBRARY = lib$(PACKAGE).a | ||
71 | |||
72 | ####################################################################### | ||
73 | ## PLEASE CHANGE ONLY THE FOLLOWING LINES | ||
74 | ## | ||
75 | |||
76 | LIBS = | ||
77 | |||
78 | HEADERS = $(PACKAGE).h \ | ||
79 | config.h \ | ||
80 | defines.h \ | ||
81 | types.h \ | ||
82 | return_values.h \ | ||
83 | inlines.h \ | ||
84 | functions.h | ||
85 | |||
86 | SOURCES = $(PACKAGE)-page.c \ | ||
87 | $(PACKAGE)-slab.c | ||
88 | |||
89 | OBJECTS = $(SOURCES:.c=.o) | ||
90 | |||
91 | DEPENDENCIES = $(SOURCES:.c=.d) | ||
92 | |||
93 | HEADER_PATH = $(PREFIX)/headers/$(PACKAGE)/. | ||
94 | |||
95 | ####################################################################### | ||
96 | ## PLEASE CONSIDER THERE IS NOTHING TO CHANGE IN THE FOLLOWING LINES | ||
97 | ## SINCE THERE ARE COMMON FOR ALL LIBRARY | ||
98 | ## | ||
99 | |||
100 | %.o: %.c | ||
101 | @echo "Compiling" $<... | ||
102 | @$(CC) -o $(@) $(CFLAGS) $(INCLUDES) -c $< | ||
103 | @$(CC) -M $< $(CFLAGS) $(INCLUDES) > $(*F).d | ||
104 | |||
105 | %.o: %.s | ||
106 | @echo "Assembling" $<... | ||
107 | @$(CC) -o $(@) $(CFLAGS) $(INCLUDES) -c $< | ||
108 | @$(CC) -M $< $(CFLAGS) $(INCLUDES) > $(*F).d | ||
109 | |||
110 | .PHONY: splash all clean backup restore dist install | ||
111 | |||
112 | all: splash $(LIBRARY) test | ||
113 | |||
114 | splash: | ||
115 | @echo "<<< " $(PACKAGE) "-" $(VERSION) ">>>" | ||
116 | |||
117 | #################################################### | ||
118 | # LIBRAY PART : | ||
119 | |||
120 | $(LIBRARY): $(OBJECTS) | ||
121 | @echo "Creating library" $(LIBRARY)... | ||
122 | @$(AR) cru $(@) $(OBJECTS) | ||
123 | @$(RL) $(@) | ||
124 | |||
125 | |||
126 | #################################################### | ||
127 | # TEST PART : | ||
128 | |||
129 | test: test.tab.o test.lex.o $(LIBRARY) | ||
130 | @echo "Creating executable" $@... | ||
131 | @$(CC) $(INCLUDES) -g -o $(@) $(+) -lfl -lreadline | ||
132 | |||
133 | test.tab.o: test.tab.c | ||
134 | @echo "Compiling" $<... | ||
135 | @$(CC) -I. -g -o $(@) -O3 -fomit-frame-pointer -c test.tab.c | ||
136 | |||
137 | test.lex.o: test.lex.c | ||
138 | @echo "Compiling" $<... | ||
139 | @$(CC) -I. -g -o $(@) -O3 -fomit-frame-pointer -c test.lex.c | ||
140 | |||
141 | test.tab.h: test.tab.c | ||
142 | |||
143 | test.lex.c: test.l test.tab.h | ||
144 | @echo "Flex:" $< | ||
145 | @flex -otest.lex.c test.l | ||
146 | |||
147 | test.tab.c: test.y | ||
148 | @echo "Bison:" $< | ||
149 | @bison -d test.y | ||
150 | |||
151 | |||
152 | #################################################### | ||
153 | # MISCELLANOUS PART : | ||
154 | |||
155 | clean: | ||
156 | @rm -f $(LIBRARY) | ||
157 | @rm -f $(OBJECTS) test.lex.o test.tab.o | ||
158 | @rm -f $(DEPENDENCIES) | ||
159 | @rm -f *~ test test.exe | ||
160 | @rm -f test.tab.h test.tab.c test.lex.c | ||
161 | @rm -f core | ||
162 | |||
163 | backup: | ||
164 | @mkdir -p ./backup | ||
165 | @cp -f makefile ./backup | ||
166 | @cp -f test.l ./backup | ||
167 | @cp -f test.y ./backup | ||
168 | @cp -f $(SOURCES:.c=.txt) ./backup | ||
169 | @for header in $(HEADERS) ; do cp -f $$header ./backup ; done | ||
170 | @for source in $(SOURCES) ; do cp -f $$source ./backup ; done | ||
171 | |||
172 | restore: | ||
173 | @cp -f ./backup/makefile . | ||
174 | @cp -f ./backup/test.l . | ||
175 | @cp -f ./backup/test.y . | ||
176 | @cp -f ./backup/$(SOURCES:.c=.txt) | ||
177 | @for header in $(HEADERS) ; do cp -f ./backup/$$header . ; done | ||
178 | @for source in $(SOURCES) ; do cp -f ./backup/$$source . ; done | ||
179 | |||
180 | dist: backup | ||
181 | @mv backup $(PACKAGE) | ||
182 | @tar czvf $(PACKAGE)-$(VERSION).tar.gz $(PACKAGE)/* | ||
183 | @rm -f $(PACKAGE)/* | ||
184 | @rmdir $(PACKAGE) | ||
185 | |||
186 | install: all | ||
187 | @mkdir -p $(PREFIX)/libraries | ||
188 | @cp $(LIBRARY) $(PREFIX)/libraries | ||
189 | @mkdir -p $(PREFIX)/headers/$(PACKAGE) | ||
190 | @for header in $(HEADERS) ; do cp $$header $(PREFIX)/headers/$(PACKAGE) ; done | ||
191 | |||
192 | -include $(DEPENDENCIES) | ||
193 | |||
diff --git a/firmware/test/memory/memory-page.c b/firmware/test/memory/memory-page.c new file mode 100644 index 0000000000..5ec46ec810 --- /dev/null +++ b/firmware/test/memory/memory-page.c | |||
@@ -0,0 +1,434 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id: | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #include <memory.h> | ||
20 | |||
21 | #define LESS -1 | ||
22 | #define MORE +1 | ||
23 | |||
24 | #ifdef TEST | ||
25 | |||
26 | struct memory_free_page free_page[MEMORY_TOTAL_PAGES]; | ||
27 | |||
28 | static inline unsigned int get_offset (int order) | ||
29 | { | ||
30 | return (2 << order); | ||
31 | } | ||
32 | |||
33 | // IA32 has no problem with shift operation | ||
34 | static inline unsigned int get_size (int order) | ||
35 | { | ||
36 | return (MEMORY_PAGE_MINIMAL_SIZE << order); | ||
37 | } | ||
38 | |||
39 | // Arghhhh ! I cannot align 'free_page' on 512-byte boundary (max is 16-byte for Cygwin) | ||
40 | static inline struct memory_free_page *get_neighbour (struct memory_free_page *node,unsigned int size) | ||
41 | { | ||
42 | return ((struct memory_free_page *)((unsigned)free_page + (((unsigned)node - (unsigned)free_page) ^ size))); | ||
43 | } | ||
44 | |||
45 | #else | ||
46 | |||
47 | extern struct memory_free_page free_page[MEMORY_TOTAL_PAGES] asm("dram"); | ||
48 | |||
49 | static inline unsigned int get_offset (int order) | ||
50 | { | ||
51 | static unsigned short offset [MEMORY_TOTAL_ORDERS] = | ||
52 | { 2,4,8,16,32,64,128,256,512,1024,2048,4096,8192 }; | ||
53 | return offset[order]; | ||
54 | } | ||
55 | |||
56 | // SH1 has very poor shift instructions (only <<1,>>1,<<2,>>2,<<8,>>8,<<16 and >>16). | ||
57 | // so we should use a lookup table to speedup. | ||
58 | static inline unsigned int get_size (int order) | ||
59 | { | ||
60 | return (get_offset (order))<<8; | ||
61 | } | ||
62 | |||
63 | static inline struct memory_free_page *get_neighbour (struct memory_free_page *node,unsigned int size) | ||
64 | { | ||
65 | return ((struct memory_free_page *)((unsigned)node ^ size)); | ||
66 | } | ||
67 | |||
68 | #endif | ||
69 | |||
70 | static char free_page_order[MEMORY_TOTAL_PAGES]; | ||
71 | static struct memory_free_page *free_page_list[MEMORY_TOTAL_ORDERS]; | ||
72 | |||
73 | static inline int get_order (struct memory_free_page *node) | ||
74 | { | ||
75 | return free_page_order[node - free_page]; | ||
76 | } | ||
77 | static inline void set_order (struct memory_free_page *node,int order) | ||
78 | { | ||
79 | free_page_order[node - free_page] = order; | ||
80 | } | ||
81 | |||
82 | #if MEMORY_PAGE_USE_SPLAY_TREE | ||
83 | |||
84 | # include <stdio.h> | ||
85 | |||
86 | static struct memory_free_page *splay_page (struct memory_free_page *root,struct memory_free_page *node) | ||
87 | { | ||
88 | struct memory_free_page *down; | ||
89 | struct memory_free_page *less; | ||
90 | struct memory_free_page *more; | ||
91 | struct memory_free_page head; | ||
92 | head.less = | ||
93 | head.more = 0; | ||
94 | less = | ||
95 | more = &head; | ||
96 | while (1) | ||
97 | { | ||
98 | if (node < root) | ||
99 | { | ||
100 | if ((down = root->less)) | ||
101 | { | ||
102 | if (node < down) | ||
103 | { | ||
104 | root->less = down->more; | ||
105 | down->more = root; | ||
106 | root = down; | ||
107 | if (!root->less) | ||
108 | break; | ||
109 | } | ||
110 | more->less = root; | ||
111 | more = root; | ||
112 | root = root->less; | ||
113 | continue; | ||
114 | } | ||
115 | break; | ||
116 | } | ||
117 | if (root < node) | ||
118 | { | ||
119 | if ((down = root->more)) | ||
120 | { | ||
121 | if (root < node) | ||
122 | { | ||
123 | root->more = down->less; | ||
124 | down->less = root; | ||
125 | root = down; | ||
126 | if (!root->more) | ||
127 | break; | ||
128 | } | ||
129 | less->more = root; | ||
130 | less = root; | ||
131 | root = root->more; | ||
132 | continue; | ||
133 | } | ||
134 | } | ||
135 | break; | ||
136 | } | ||
137 | less->more = root->less; | ||
138 | more->less = root->more; | ||
139 | root->less = head.more; | ||
140 | root->more = head.less; | ||
141 | return root; | ||
142 | } | ||
143 | |||
144 | static inline void insert_page (int order,struct memory_free_page *node) | ||
145 | { | ||
146 | struct memory_free_page *root = free_page_list[order]; | ||
147 | if (!root) | ||
148 | { | ||
149 | node->less = | ||
150 | node->more = 0; | ||
151 | } | ||
152 | else if (node < (root = splay_page (root,node))) | ||
153 | { | ||
154 | node->less = root->less; | ||
155 | node->more = root; | ||
156 | root->less = 0; | ||
157 | } | ||
158 | else if (node > root) | ||
159 | { | ||
160 | node->less = root; | ||
161 | node->more = root->more; | ||
162 | node->more = 0; | ||
163 | } | ||
164 | free_page_list[order] = node; | ||
165 | set_order (node,order); | ||
166 | return; | ||
167 | } | ||
168 | |||
169 | static inline struct memory_free_page *pop_page (int order,int want) | ||
170 | { | ||
171 | struct memory_free_page *root = free_page_list[order]; | ||
172 | if (root) | ||
173 | { | ||
174 | root = splay_page (root,free_page); | ||
175 | free_page_list[order] = root->more; | ||
176 | set_order (root,~want); | ||
177 | } | ||
178 | return root; | ||
179 | } | ||
180 | |||
181 | static inline void remove_page (int order,struct memory_free_page *node) | ||
182 | { | ||
183 | struct memory_free_page *root = free_page_list[order]; | ||
184 | root = splay_page (root,node); | ||
185 | if (root->less) | ||
186 | { | ||
187 | node = splay_page (root->less,node); | ||
188 | node->more = root->more; | ||
189 | } | ||
190 | else | ||
191 | node = root->more; | ||
192 | free_page_list[order] = node; | ||
193 | } | ||
194 | |||
195 | #else | ||
196 | |||
197 | static inline void insert_page (int order,struct memory_free_page *node) | ||
198 | { | ||
199 | struct memory_free_page *head = free_page_list[order]; | ||
200 | node->less = 0; | ||
201 | node->more = head; | ||
202 | if (head) | ||
203 | head->less = node; | ||
204 | free_page_list[order] = node; | ||
205 | set_order (node,order); | ||
206 | } | ||
207 | |||
208 | static inline struct memory_free_page *pop_page (int order,int want) | ||
209 | { | ||
210 | struct memory_free_page *node = free_page_list[order]; | ||
211 | if (node) | ||
212 | { | ||
213 | free_page_list[order] = node->more; | ||
214 | if (node->more) | ||
215 | node->more->less = 0; | ||
216 | set_order (node,~want); | ||
217 | } | ||
218 | return node; | ||
219 | } | ||
220 | |||
221 | static inline void remove_page (int order,struct memory_free_page *node) | ||
222 | { | ||
223 | if (node->less) | ||
224 | node->less->more = node->more; | ||
225 | else | ||
226 | free_page_list[order] = node->more; | ||
227 | if (node->more) | ||
228 | node->more->less = node->less; | ||
229 | } | ||
230 | |||
231 | #endif | ||
232 | |||
233 | static inline void push_page (int order,struct memory_free_page *node) | ||
234 | { | ||
235 | node->less = 0; | ||
236 | node->more = 0; | ||
237 | free_page_list[order] = node; | ||
238 | set_order (node,order); | ||
239 | } | ||
240 | |||
241 | static struct memory_free_page *allocate_page (unsigned int size,int order) | ||
242 | { | ||
243 | struct memory_free_page *node; | ||
244 | int min = order; | ||
245 | while ((unsigned)order <= (MEMORY_TOTAL_ORDERS - 1)) | ||
246 | // order is valid ? | ||
247 | { | ||
248 | if (!(node = pop_page (order,min))) | ||
249 | // no free page of this order ? | ||
250 | { | ||
251 | ++order; size <<= 1; | ||
252 | continue; | ||
253 | } | ||
254 | while (order > min) | ||
255 | // split our larger page in smaller pages | ||
256 | { | ||
257 | --order; size >>= 1; | ||
258 | push_page (order,(struct memory_free_page *)((unsigned int)node + size)); | ||
259 | } | ||
260 | return node; | ||
261 | } | ||
262 | return MEMORY_RETURN_FAILURE; | ||
263 | } | ||
264 | |||
265 | static inline void release_page (struct memory_free_page *node,unsigned int size,int order) | ||
266 | { | ||
267 | struct memory_free_page *neighbour; | ||
268 | while ((order <= (MEMORY_TOTAL_ORDERS - 1)) && | ||
269 | ((neighbour = get_neighbour (node,size)), | ||
270 | (get_order (neighbour) == order))) | ||
271 | // merge our released page with its contiguous page into a larger page | ||
272 | { | ||
273 | remove_page (order,neighbour); | ||
274 | ++order; size <<= 1; | ||
275 | if (neighbour < node) | ||
276 | node = neighbour; | ||
277 | } | ||
278 | insert_page (order,node); | ||
279 | } | ||
280 | |||
281 | |||
282 | /*****************************************************************************/ | ||
283 | /* PUBLIC FUNCTIONS */ | ||
284 | /*****************************************************************************/ | ||
285 | |||
286 | void *memory_allocate_page (int order) | ||
287 | { | ||
288 | if (order < 0) | ||
289 | return MEMORY_RETURN_FAILURE; | ||
290 | return allocate_page (get_size (order),order); | ||
291 | } | ||
292 | |||
293 | // release a page : | ||
294 | // when called, 'address' MUST be a valid address pointing | ||
295 | // to &dram[i], where i ranges from 0 to MEMORY_TOTAL_PAGES - 1. | ||
296 | // FAILURE if block is already freed. | ||
297 | int memory_release_page (void *address) | ||
298 | { | ||
299 | struct memory_free_page *node = (struct memory_free_page *)address; | ||
300 | int order = ~get_order (node); | ||
301 | if (order < 0) | ||
302 | return MEMORY_RETURN_FAILURE; | ||
303 | release_page (node,get_size (order),order); | ||
304 | return MEMORY_RETURN_SUCCESS; | ||
305 | } | ||
306 | |||
307 | /* NOT VERY OPTIMIZED AT ALL BUT WE WILL DO IT WHEN PRIORITY COMES */ | ||
308 | void memory_copy (void *target,void const *source,unsigned int count) | ||
309 | { | ||
310 | while (count--) | ||
311 | *((char *)target)++ = *((char const *)source)++; | ||
312 | } | ||
313 | |||
314 | /* NOT VERY OPTIMIZED AT ALL BUT WE WILL DO IT WHEN PRIORITY COMES */ | ||
315 | void memory_set (void *target,int byte,unsigned int count) | ||
316 | { | ||
317 | while (count--) | ||
318 | *((char *)target)++ = (char)byte; | ||
319 | } | ||
320 | |||
321 | void memory_setup (void) | ||
322 | { | ||
323 | #if 0 | ||
324 | memory_set (free_page,0,MEMORY_TOTAL_BYTES); | ||
325 | memory_set (free_page_list,0,MEMORY_TOTAL_ORDERS *sizeof (struct memory_free_page *)); | ||
326 | #endif | ||
327 | memory_set (free_page_order + 1,(MEMORY_TOTAL_ORDERS - 1),MEMORY_TOTAL_PAGES); | ||
328 | free_page_order[0] = MEMORY_TOTAL_ORDERS - 1; | ||
329 | free_page_list[MEMORY_TOTAL_ORDERS - 1] = free_page; | ||
330 | } | ||
331 | |||
332 | #ifdef TEST | ||
333 | # include <stdio.h> | ||
334 | # include <stdlib.h> | ||
335 | # if MEMORY_PAGE_USE_SPLAY_TREE | ||
336 | |||
337 | static void dump_splay_node (struct memory_free_page *node,int level) | ||
338 | { | ||
339 | if (!node) | ||
340 | return; | ||
341 | dump_splay_node (node->less,level+1); | ||
342 | printf ("\n%*s[%d-%d]",level,"",(node - free_page),(node - free_page) + (1 << get_order (node)) - 1); | ||
343 | dump_splay_node (node->more,level+1); | ||
344 | } | ||
345 | |||
346 | static void dump_splay_tree (struct memory_free_page *root) | ||
347 | { | ||
348 | dump_splay_node (root,2); fflush (stdout); | ||
349 | } | ||
350 | |||
351 | # endif | ||
352 | |||
353 | void memory_spy_page (void *address) | ||
354 | { | ||
355 | struct memory_free_page *node = (struct memory_free_page *)address; | ||
356 | int order,used; | ||
357 | if (node) | ||
358 | { | ||
359 | order = get_order (node); | ||
360 | used = order < 0; | ||
361 | if (used) | ||
362 | order = ~order; | ||
363 | printf("\n(%s,%2d,%7d)",(used ? "used" : "free"),order,get_size (order)); | ||
364 | } | ||
365 | } | ||
366 | |||
367 | void memory_dump (int order) | ||
368 | { | ||
369 | struct memory_free_page *node = free_page_list[order]; | ||
370 | printf("\n(%s,%2d,%7d)",node ? "free" : "none",order,get_size (order)); | ||
371 | # if MEMORY_PAGE_USE_SPLAY_TREE | ||
372 | dump_splay_tree (node); | ||
373 | # else | ||
374 | while (node) | ||
375 | { | ||
376 | printf("[%d-%d]",(node - free_page),(node - free_page) + (1<<order) - 1); | ||
377 | node = node->more; | ||
378 | } | ||
379 | # endif | ||
380 | |||
381 | } | ||
382 | |||
383 | void memory_check (int order) | ||
384 | { | ||
385 | struct memory_free_page *node[4096],*swap; | ||
386 | unsigned int i = 0,j = 0; | ||
387 | while (i <= 12) | ||
388 | memory_dump (i++); | ||
389 | i = 0; | ||
390 | printf ("\nallocating...\n"); | ||
391 | while (order >= 0) | ||
392 | { | ||
393 | j = order; | ||
394 | while ((swap = memory_allocate_page (j))) | ||
395 | { | ||
396 | node[i++] = swap; | ||
397 | printf("[%d-%d]",(swap - free_page),(swap - free_page) + ((1 << j)-1)); | ||
398 | for (j += (rand () & 15); j > (unsigned int)order; j -= order); | ||
399 | } | ||
400 | --order; | ||
401 | } | ||
402 | node[i] = 0; | ||
403 | while (j <= 12) | ||
404 | memory_dump (j++); | ||
405 | j = 0; | ||
406 | printf ("\nreleasing..."); | ||
407 | --i; | ||
408 | while (i > 0) | ||
409 | { | ||
410 | unsigned int k = 0; | ||
411 | printf ("\n"); | ||
412 | swap = node[k++]; | ||
413 | #if 0 | ||
414 | while (swap) | ||
415 | { | ||
416 | printf("[%d-%d]",(swap - free_page),(swap - free_page) + ((1 << ~get_order (swap))-1)); | ||
417 | swap = node[k++]; | ||
418 | } | ||
419 | #endif | ||
420 | for (j += 1 + (rand () & 15); j >= i; j -= i); | ||
421 | swap = node[j]; | ||
422 | node[j] = node[i]; | ||
423 | memory_release_page (swap); | ||
424 | node[i] = 0; | ||
425 | --i; | ||
426 | } | ||
427 | memory_release_page (node[0]); | ||
428 | i = 0; | ||
429 | while (i <= 12) | ||
430 | memory_dump (i++); | ||
431 | printf("\n\n%s !",(get_order (free_page) == 12) ? "SUCCESS" : "FAILURE"); | ||
432 | } | ||
433 | |||
434 | #endif | ||
diff --git a/firmware/test/memory/memory-slab.c b/firmware/test/memory/memory-slab.c new file mode 100644 index 0000000000..289818b24a --- /dev/null +++ b/firmware/test/memory/memory-slab.c | |||
@@ -0,0 +1,463 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id: | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #if 0 | ||
20 | |||
21 | #include <memory.h> | ||
22 | |||
23 | static struct memory_cache *free_block_cache[MEMORY_PAGE_MINIMAL_SIZE - ]; | ||
24 | static struct memory_cache *cache_list; | ||
25 | |||
26 | static inline int get_order (unsigned size) | ||
27 | { | ||
28 | int order = 0; | ||
29 | size = (size + sizeof(struct memory_free_block) - 1) & - sizeof(struct memory_free_block); | ||
30 | while (size > 0) | ||
31 | { | ||
32 | ++order; size <<= 1; | ||
33 | } | ||
34 | return order; | ||
35 | } | ||
36 | |||
37 | static inline struct memory_slab *get_slab (struct memory_cache *cache,void *address) | ||
38 | { | ||
39 | #ifdef TEST | ||
40 | return (struct memory_slab *)((((unsigned)address + cache->page_size) & -cache->page_size) - sizeof (struct memory_slab)); | ||
41 | #else | ||
42 | return (struct memory_slab *)((free_page + (((unsigned)address - free_page + cache->page_size) & -cache->page_size) - sizeof (struct memory_slab))); | ||
43 | #endif | ||
44 | } | ||
45 | |||
46 | static struct memory_cache *splay_cache (struct memory_cache *root,unsigned int left) | ||
47 | { | ||
48 | struct memory_cache *down; | ||
49 | struct memory_cache *less; | ||
50 | struct memory_cache *more; | ||
51 | struct memory_cache head; | ||
52 | head.less = | ||
53 | head.more = 0; | ||
54 | less = | ||
55 | more = &head; | ||
56 | while (1) | ||
57 | { | ||
58 | if (left < root->left) | ||
59 | { | ||
60 | if ((down = root->less)) | ||
61 | { | ||
62 | if (left < down->left) | ||
63 | { | ||
64 | root->less = down->more; | ||
65 | down->more = root; | ||
66 | root = down; | ||
67 | if (!root->less) | ||
68 | break; | ||
69 | } | ||
70 | more->less = root; | ||
71 | more = root; | ||
72 | root = root->less; | ||
73 | continue; | ||
74 | } | ||
75 | break; | ||
76 | } | ||
77 | if (root->left < left) | ||
78 | { | ||
79 | if ((down = root->more)) | ||
80 | { | ||
81 | if (root->left < left) | ||
82 | { | ||
83 | root->more = down->less; | ||
84 | down->less = root; | ||
85 | root = down; | ||
86 | if (!root->more) | ||
87 | break; | ||
88 | } | ||
89 | less->more = root; | ||
90 | less = root; | ||
91 | root = root->more; | ||
92 | continue; | ||
93 | } | ||
94 | } | ||
95 | break; | ||
96 | } | ||
97 | less->more = root->less; | ||
98 | more->less = root->more; | ||
99 | root->less = head.more; | ||
100 | root->more = head.less; | ||
101 | return root; | ||
102 | } | ||
103 | |||
104 | static inline struct memory_cache *insert_cache (struct memory_cache *root,struct memory_cache *node) | ||
105 | { | ||
106 | node->less = | ||
107 | node->more = | ||
108 | node->same = 0; | ||
109 | if (root) | ||
110 | { | ||
111 | if (node->left == ((root = splay_cache (root,node))->left)) | ||
112 | { | ||
113 | node->less = root.less; | ||
114 | node->more = root.more; | ||
115 | node->same = root; | ||
116 | root->less = node; | ||
117 | } | ||
118 | else if (node < root) | ||
119 | { | ||
120 | node->less = root->less; | ||
121 | node->more = root; | ||
122 | root->less = 0; | ||
123 | } | ||
124 | else | ||
125 | { | ||
126 | node->less = root; | ||
127 | node->more = root->more; | ||
128 | node->more = 0; | ||
129 | } | ||
130 | } | ||
131 | return node; | ||
132 | } | ||
133 | |||
134 | static inline struct memory_cache *remove_cache (struct memory_cache *root,struct memory_cache *node) | ||
135 | { | ||
136 | if (root) | ||
137 | { | ||
138 | root = splay_cache (root,node); | ||
139 | if (root != node) | ||
140 | { | ||
141 | node->less->same = node->same; | ||
142 | if (node->same) | ||
143 | node->same->less = node->less; | ||
144 | return root; | ||
145 | } | ||
146 | if (root->less) | ||
147 | { | ||
148 | node = splay_page (root->less,node); | ||
149 | node->more = root->more; | ||
150 | } | ||
151 | else | ||
152 | node = root->more; | ||
153 | } | ||
154 | return root; | ||
155 | } | ||
156 | |||
157 | static inline struct memory_cache *move_cache (struct memory_cache *root,struct memory_cache *node,int delta) | ||
158 | { | ||
159 | if ((root = remove_cache (root,node))) | ||
160 | { | ||
161 | node->left += delta; | ||
162 | root = insert_cache (root,node); | ||
163 | } | ||
164 | return root; | ||
165 | } | ||
166 | |||
167 | static inline struct memory_slab *push_slab (struct memory_cache *head,struct memory_cache *node) | ||
168 | { | ||
169 | node->less = head; | ||
170 | if (head) | ||
171 | { | ||
172 | node->more = head->more; | ||
173 | head->more = node; | ||
174 | } | ||
175 | else | ||
176 | node->more = 0; | ||
177 | return node; | ||
178 | } | ||
179 | |||
180 | static inline struct memory_slab *pop_slab (struct memory_cache *head,struct memory_cache *node) | ||
181 | { | ||
182 | if (head) | ||
183 | head->more = node->more; | ||
184 | return node->more; | ||
185 | } | ||
186 | |||
187 | static inline struct memory_slab *move_slab (struct memory_slab **from,struct memory_slab **to) | ||
188 | { | ||
189 | struct memory_slab *head = *from; | ||
190 | *from = (*from)->more; | ||
191 | if (*from) | ||
192 | (*from)->less = head->less; | ||
193 | head->less = 0; | ||
194 | head->more = (*to); | ||
195 | if (*to) | ||
196 | (*to)->prev = head; | ||
197 | *to = head; | ||
198 | return head; | ||
199 | } | ||
200 | |||
201 | |||
202 | /*****************************************************************************/ | ||
203 | /* PUBLIC FUNCTIONS */ | ||
204 | /*****************************************************************************/ | ||
205 | |||
206 | /////////////////////////////////////////////////////////////////////////////// | ||
207 | // MEMORY CACHE : | ||
208 | ///////////////// | ||
209 | // | ||
210 | // - memory_grow_cache : allocate a new slab for a cache | ||
211 | // - memory_shrink_cache : release free slabs from a cache | ||
212 | // - memory_create_cache : create a new cache of size-fixed blocks | ||
213 | // - memory_destroy_cache : destroy the cache and release all the slabs | ||
214 | // - memory_cache_allocate : allocate a block from the cache | ||
215 | // - memory_cache_release : release a block in the cache | ||
216 | // | ||
217 | |||
218 | struct memory_slab *memory_grow_cache (struct memory_cache *cache) | ||
219 | { | ||
220 | struct memory_slab *slab; | ||
221 | unsigned int page; | ||
222 | if (cache) | ||
223 | { | ||
224 | page = (unsigned int)memory_allocate_page (cache->page_order); | ||
225 | if (page) | ||
226 | { | ||
227 | struct memory_free_block *block,**link; | ||
228 | slab = (struct memory_slab *)(page + cache->page_size - sizeof (struct memory_slab)); | ||
229 | slab->free = 0; | ||
230 | slab->left = 0; | ||
231 | link = &slab->free; | ||
232 | for ((unsigned int)block = page; | ||
233 | (unsigned int)block + cache->size < (unsigned int)slab; | ||
234 | (unsigned int)block += cache->size) | ||
235 | { | ||
236 | *link = block; | ||
237 | link = &block->link; | ||
238 | ++slab->free; | ||
239 | } | ||
240 | *link = 0; | ||
241 | cache->blocks_per_slab = slab->free; | ||
242 | cache->reap = push_slab (cache->reap,slab); | ||
243 | cache_list = move_cache (cache_list,cache,+1); | ||
244 | return slab; | ||
245 | } | ||
246 | } | ||
247 | return MEMORY_RETURN_FAILURE; | ||
248 | } | ||
249 | |||
250 | static int memory_shrink_cache (struct memory_cache *cache,int all,int move) | ||
251 | { | ||
252 | struct memory_slab *slab; | ||
253 | unsigned int slabs = 0; | ||
254 | if (cache) | ||
255 | { | ||
256 | while ((slab = cache->reap)) | ||
257 | { | ||
258 | ++slabs; | ||
259 | cache->reap = pop_slab (cache->reap,slab); | ||
260 | memory_release_page ((void *)slab); | ||
261 | if (all) | ||
262 | continue; | ||
263 | if (move) | ||
264 | cache_list = move_cache (cache_list,cache,-slabs); | ||
265 | return MEMORY_RETURN_SUCCESS; | ||
266 | } | ||
267 | } | ||
268 | return MEMORY_RETURN_FAILURE; | ||
269 | } | ||
270 | |||
271 | int memory_shrink_cache (struct memory_cache *cache,int all) | ||
272 | { | ||
273 | return shrink_cache (cache,all,1 /* move cache in cache_list */); | ||
274 | } | ||
275 | |||
276 | struct memory_cache *memory_create_cache (unsigned int size,int align,int flags) | ||
277 | { | ||
278 | struct memory_cache *cache; | ||
279 | unsigned int waste = 0,blocks_per_page; | ||
280 | int page_order; | ||
281 | unsigned int page_size; | ||
282 | unsigned int original_size = size; | ||
283 | |||
284 | // Align size on 'align' bytes ('align' should equal 1<<n) | ||
285 | // if 'align' is inferior to 4, 32-bit word alignment is done by default. | ||
286 | size = (align > 4) ? ((size + align - 1) & -align) : ((size + sizeof (int) - 1) & -sizeof (int)); | ||
287 | if (!(cache = memory_cache_allocate (&cache_cache)) | ||
288 | return MEMORY_RETURN_FAILURE; | ||
289 | |||
290 | cache->flags = | ||
291 | cache->left = 0; | ||
292 | |||
293 | cache->used = | ||
294 | cache->free = | ||
295 | cache->reap = 0; | ||
296 | |||
297 | cache->original_size = original_size; | ||
298 | cache->size = size; | ||
299 | |||
300 | page_size = 0; | ||
301 | page_order = MEMORY_PAGE_MINIMAL_SIZE;; | ||
302 | |||
303 | // Trying to determine what is the best number of pages per slab | ||
304 | for (;; ++order,(page_size <<= 1)) | ||
305 | { | ||
306 | if (page_order >= MEMORY_MAXIMUM_PAGE_ORDER_PER_SLAB) | ||
307 | { | ||
308 | memory_cache_release (&cache_cache,cache); | ||
309 | return MEMORY_RETURN_FAILURE; | ||
310 | } | ||
311 | |||
312 | waste = page_size; | ||
313 | waste -= sizeof (struct memory_slab); | ||
314 | |||
315 | blocks_per_slab = waste / size; | ||
316 | waste -= block_per_slab * size; | ||
317 | |||
318 | if (blocks_per_slab < MEMORY_MINIMUM_BLOCKS_PER_SLAB) | ||
319 | { | ||
320 | ++page_order; page_size <<= 1; | ||
321 | continue; | ||
322 | } | ||
323 | |||
324 | // below 3% of lost space is correct | ||
325 | if ((waste << 16) / page_size) < 1967) | ||
326 | break; | ||
327 | ++page_order; page_size <<= 1; | ||
328 | } | ||
329 | |||
330 | cache->page_size = page_size; | ||
331 | cache->page_order = page_order; | ||
332 | |||
333 | cache_list = insert_cache (cache_list,cache); | ||
334 | |||
335 | return cache; | ||
336 | } | ||
337 | |||
338 | int memory_destroy_cache (struct memory_cache *cache) | ||
339 | { | ||
340 | if (cache) | ||
341 | { | ||
342 | cache_list = remove_cache (cache_list,cache); | ||
343 | if (shrink_cache (cache,1 /* release all free slabs */,0 /* don't move in cache_list */)) | ||
344 | return memory_cache_release (&cache_cache,cache); | ||
345 | } | ||
346 | return MEMORY_RETURN_FAILURE; | ||
347 | } | ||
348 | |||
349 | void *memory_cache_allocate (struct memory_cache *cache) | ||
350 | { | ||
351 | if (cache) | ||
352 | { | ||
353 | do | ||
354 | { | ||
355 | struct memory_slab *slab; | ||
356 | if ((slab = cache->free)) | ||
357 | { | ||
358 | if (slab->left > 0) | ||
359 | { | ||
360 | ok: struct memory_free_block *block = slab->free; | ||
361 | slab->free = block->link; | ||
362 | if (--slab->left == 0) | ||
363 | move_slab (&cache->free,&cache->used); | ||
364 | return block; | ||
365 | } | ||
366 | } | ||
367 | if (cache->reap) | ||
368 | { | ||
369 | slab = move_slab (&cache->reap,&cache->free); | ||
370 | cache_list = move_cache (cache_list,cache,-1); | ||
371 | goto ok; | ||
372 | } | ||
373 | } | ||
374 | while (grow_cache (cache)); | ||
375 | } | ||
376 | return MEMORY_RETURN_FAILURE; | ||
377 | } | ||
378 | |||
379 | int memory_cache_release (struct memory_cache *cache,void *address) | ||
380 | { | ||
381 | struct memory_slab *slab = get_slab (cache,address); | ||
382 | slab->free = (struct memory_free_block *)address; | ||
383 | if (slab->left++ == 0) | ||
384 | move_slab (&cache->used,&cache->free); | ||
385 | else if (slab->left == cache->elements_per_slab) | ||
386 | { | ||
387 | move_slab (&cache->free,&cache->reap); | ||
388 | cache_list = move_cache (cache_list,cache,+1); | ||
389 | } | ||
390 | return MEMORY_RETURN_SUCCESS; | ||
391 | } | ||
392 | |||
393 | |||
394 | /////////////////////////////////////////////////////////////////////////////// | ||
395 | // MEMORY BLOCK : | ||
396 | ///////////////// | ||
397 | // | ||
398 | // - memory_allocate_small_block : allocate a small block (no page) | ||
399 | // - memory_release_small_block : release a small block (no page) | ||
400 | // - memory_allocate_block : allocate a block (or a page) | ||
401 | // - memory_release_block : release a block (or a page) | ||
402 | // | ||
403 | |||
404 | static inline void *allocate_small_block (int order) | ||
405 | { | ||
406 | struct memory_cache *cache = free_block_cache[order]; | ||
407 | do | ||
408 | { | ||
409 | if (cache) | ||
410 | return memory_cache_allocate (cache); | ||
411 | } | ||
412 | while ((free_block_cache[order] = cache = memory_create_cache (size,0,0))); | ||
413 | return MEMORY_RETURN_FAILURE; | ||
414 | } | ||
415 | |||
416 | void *memory_allocate_small_block (int order) | ||
417 | { | ||
418 | if (order < MEMORY_PAGE_MINIMAL_ORDER) | ||
419 | return allocate_small_block (order) | ||
420 | return MEMORY_RETURN_FAILURE; | ||
421 | } | ||
422 | |||
423 | static inline int release_small_block (int order,void *address) | ||
424 | { | ||
425 | struct memory_cache *cache = free_block_cache[order]; | ||
426 | if (cache) | ||
427 | return memory_cache_release (cache,address); | ||
428 | return MEMORY_RETURN_FAILURE; | ||
429 | } | ||
430 | |||
431 | int memory_release_small_block (int order,void *address) | ||
432 | { | ||
433 | if (order < MEMORY_PAGE_MINIMAL_ORDER) | ||
434 | return memory_release_small_block (order,address); | ||
435 | return memory_release_page (address); | ||
436 | } | ||
437 | |||
438 | void *memory_allocate_block (unsigned int size) | ||
439 | { | ||
440 | size += sizeof (int *); | ||
441 | int order = get_order (size); | ||
442 | if (size < MEMORY_PAGE_MINIMAL_SIZE) | ||
443 | { | ||
444 | int *block = (int *)allocate_block (order); | ||
445 | *block = order; | ||
446 | return block; | ||
447 | } | ||
448 | if (size < MEMORY_PAGE_MAXIMAL_SIZE) | ||
449 | return memory_allocate_page (order); | ||
450 | return MEMORY_RETURN_FAILURE; | ||
451 | } | ||
452 | |||
453 | int memory_release_block (void *address) | ||
454 | { | ||
455 | int order = *((int *)address); | ||
456 | if (order < MEMORY_PAGE_MINIMAL_ORDER) | ||
457 | return release_block (order); | ||
458 | if (order < MEMORY_PAGE_MAXIMAL_ORDER) | ||
459 | return memory_release_page (address); | ||
460 | return MEMORY_RETURN_FAILURE; | ||
461 | } | ||
462 | |||
463 | #endif \ No newline at end of file | ||
diff --git a/firmware/test/memory/memory.h b/firmware/test/memory/memory.h new file mode 100644 index 0000000000..881cb509bc --- /dev/null +++ b/firmware/test/memory/memory.h | |||
@@ -0,0 +1,27 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef __LIBRARY_MEMORY_H__ | ||
20 | # define __LIBRARY_MEMORY_H__ | ||
21 | # include <config.h> | ||
22 | # include <defines.h> | ||
23 | # include <types.h> | ||
24 | # include <return_values.h> | ||
25 | # include <inlines.h> | ||
26 | # include <functions.h> | ||
27 | #endif | ||
diff --git a/firmware/test/memory/return_values.h b/firmware/test/memory/return_values.h new file mode 100644 index 0000000000..4546806acf --- /dev/null +++ b/firmware/test/memory/return_values.h | |||
@@ -0,0 +1,31 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id: | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef __LIBRARY_MEMORY_H__ | ||
20 | # error "This header file must be included ONLY from memory.h." | ||
21 | #endif | ||
22 | # ifndef __LIBRARY_MEMORY_RETURN_VALUES_H__ | ||
23 | #define __LIBRARY_MEMORY_RETURN_VALUES_H__ | ||
24 | |||
25 | enum | ||
26 | { | ||
27 | MEMORY_RETURN_SUCCESS = 1, | ||
28 | MEMORY_RETURN_FAILURE = 0 | ||
29 | }; | ||
30 | |||
31 | #endif \ No newline at end of file | ||
diff --git a/firmware/test/memory/test.l b/firmware/test/memory/test.l new file mode 100644 index 0000000000..7b938e9330 --- /dev/null +++ b/firmware/test/memory/test.l | |||
@@ -0,0 +1,23 @@ | |||
1 | %{ | ||
2 | #include "test.tab.h" | ||
3 | #define YY_INPUT(buf,result,max_size) \ | ||
4 | result = read_input (buf,max_size); | ||
5 | %} | ||
6 | |||
7 | %s GETNUMBER | ||
8 | |||
9 | %% | ||
10 | |||
11 | <GETNUMBER>[0-9]+ { yylval = atoi(yytext); return NUMBER;} | ||
12 | |||
13 | <INITIAL>"a"|"allocate" { BEGIN GETNUMBER; return ALLOCATE; } | ||
14 | <INITIAL>"r"|"release" { BEGIN GETNUMBER; return RELEASE; } | ||
15 | <INITIAL>"s"|"spy" { BEGIN GETNUMBER; return SPY; } | ||
16 | <INITIAL>"c"|"check" { BEGIN GETNUMBER; return CHECK; } | ||
17 | <INITIAL>"i"|"init" { return INIT; } | ||
18 | <INITIAL>"d"|"dump" { return DUMP; } | ||
19 | <INITIAL>"q"|"quit" { return QUIT; } | ||
20 | [ \t] ; | ||
21 | \n|. { BEGIN 0; return yytext[0]; } | ||
22 | %% | ||
23 | |||
diff --git a/firmware/test/memory/test.y b/firmware/test/memory/test.y new file mode 100644 index 0000000000..1c368a1ebb --- /dev/null +++ b/firmware/test/memory/test.y | |||
@@ -0,0 +1,182 @@ | |||
1 | %{ | ||
2 | #include <memory.h> | ||
3 | #include <stdlib.h> | ||
4 | #include <stdio.h> | ||
5 | #include <string.h> | ||
6 | void allocate (int); | ||
7 | void release (int); | ||
8 | void spy (int); | ||
9 | void dump (void); | ||
10 | void prompt (void); | ||
11 | %} | ||
12 | |||
13 | %token NUMBER | ||
14 | %token ALLOCATE | ||
15 | %token RELEASE | ||
16 | %token DUMP | ||
17 | %token SPY | ||
18 | %token CHECK | ||
19 | %token INIT | ||
20 | %token QUIT | ||
21 | |||
22 | %left '+' '-' | ||
23 | %left '*' '/' | ||
24 | %nonassoc UMINUS | ||
25 | |||
26 | %% | ||
27 | commands | ||
28 | : command ';' | ||
29 | { } | ||
30 | | commands command ';' | ||
31 | { } | ||
32 | | error ';' | ||
33 | { yyerrok; } | ||
34 | ; | ||
35 | |||
36 | command | ||
37 | : allocate | ||
38 | | release | ||
39 | | spy | ||
40 | | check | ||
41 | | INIT | ||
42 | { memory_setup (); } | ||
43 | | DUMP | ||
44 | { dump (); } | ||
45 | | QUIT | ||
46 | { return 0; } | ||
47 | ; | ||
48 | |||
49 | allocate | ||
50 | : ALLOCATE expression | ||
51 | { allocate (yylval); } | ||
52 | ; | ||
53 | |||
54 | release | ||
55 | : RELEASE expression | ||
56 | { release (yylval); } | ||
57 | ; | ||
58 | |||
59 | spy | ||
60 | : SPY expression | ||
61 | { spy (yylval); } | ||
62 | ; | ||
63 | |||
64 | check | ||
65 | : CHECK expression | ||
66 | { memory_check (yylval); } | ||
67 | ; | ||
68 | |||
69 | expression | ||
70 | : expression '+' expression | ||
71 | { $$ = $1 + $3; } | ||
72 | | expression '-' expression | ||
73 | { $$ = $1 - $3; } | ||
74 | | expression '*' expression | ||
75 | { $$ = $1 * $3; } | ||
76 | | expression '/' expression | ||
77 | { | ||
78 | if($3 == 0) | ||
79 | yyerror("divide by zero"); | ||
80 | else | ||
81 | $$ = $1 / $3; | ||
82 | } | ||
83 | | '-' expression %prec UMINUS | ||
84 | { | ||
85 | $$ = -$2; | ||
86 | } | ||
87 | | '(' expression ')' | ||
88 | { | ||
89 | $$ = $2; | ||
90 | } | ||
91 | | NUMBER | ||
92 | { | ||
93 | $$ = $1; | ||
94 | } | ||
95 | ; | ||
96 | |||
97 | %% | ||
98 | |||
99 | #include <readline/readline.h> | ||
100 | #include <readline/history.h> | ||
101 | |||
102 | int yyerror(char *s) | ||
103 | { | ||
104 | fprintf(stderr,"\nBad command"); | ||
105 | return 1; | ||
106 | } | ||
107 | |||
108 | void prompt (void) | ||
109 | { | ||
110 | printf("\n>"); fflush (stdout); | ||
111 | } | ||
112 | |||
113 | void allocate (int order) | ||
114 | { | ||
115 | extern char free_page[0]; | ||
116 | void *address; | ||
117 | printf("\nallocating a page of %d bytes...",512<<order); | ||
118 | if ((unsigned)order > 21) | ||
119 | printf (" bad order !"); | ||
120 | else if ((address = memory_allocate_page (order))) | ||
121 | printf (" page #%d allocated !",((char *)address - free_page) >> 9); | ||
122 | else | ||
123 | printf (" cannot allocate a page !"); | ||
124 | } | ||
125 | |||
126 | void release (int page) | ||
127 | { | ||
128 | extern char free_page[0]; | ||
129 | void *address = (void *)(free_page + (page << 9)); | ||
130 | printf("\nreleasing page #%d...",page); | ||
131 | if ((unsigned)page >= (2*1024*1024/512)) | ||
132 | printf (" bad page number !"); | ||
133 | else if (memory_release_page (address)) | ||
134 | printf (" page #%d released !",page); | ||
135 | else | ||
136 | printf (" cannot release this page !"); | ||
137 | } | ||
138 | |||
139 | void spy (int page) | ||
140 | { | ||
141 | extern char free_page[0]; | ||
142 | void *address = (void *)(free_page + (page << 9)); | ||
143 | printf("\nspying page #%d...",page); | ||
144 | if ((unsigned)page >= (2*1024*1024/512)) | ||
145 | printf (" bad page number !"); | ||
146 | else | ||
147 | memory_spy_page (address); | ||
148 | } | ||
149 | |||
150 | void dump (void) | ||
151 | { | ||
152 | int order; | ||
153 | printf("\ndumping free pages list..."); | ||
154 | for (order = 0; order < 13; ++order) | ||
155 | memory_dump (order); | ||
156 | } | ||
157 | |||
158 | int main () | ||
159 | { | ||
160 | yyparse(); | ||
161 | return 0; | ||
162 | } | ||
163 | |||
164 | int read_input (char *buffer,int max) | ||
165 | { | ||
166 | char *line = 0; | ||
167 | while (1) | ||
168 | { | ||
169 | line = readline ("\n>"); | ||
170 | if (!line) | ||
171 | break; | ||
172 | if (*line) | ||
173 | add_history(line); | ||
174 | strncpy (buffer,line,max); | ||
175 | strcat (buffer,";"); | ||
176 | free (line); | ||
177 | return strlen (buffer); | ||
178 | } | ||
179 | buffer[0] = ';'; | ||
180 | return 1; | ||
181 | } | ||
182 | |||
diff --git a/firmware/test/memory/types.h b/firmware/test/memory/types.h new file mode 100644 index 0000000000..05e97b6b26 --- /dev/null +++ b/firmware/test/memory/types.h | |||
@@ -0,0 +1,72 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id: | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef __LIBRARY_MEMORY_H__ | ||
20 | #error "This header file must be included ONLY from memory.h." | ||
21 | #endif | ||
22 | #ifndef __LIBRARY_MEMORY_TYPES_H__ | ||
23 | #define __LIBRARY_MEMORY_TYPES_H__ | ||
24 | |||
25 | struct memory_free_page | ||
26 | { | ||
27 | struct memory_free_page | ||
28 | *less,*more; | ||
29 | char | ||
30 | reserved[MEMORY_PAGE_MINIMAL_SIZE - 2*sizeof (struct memory_free_page *)]; | ||
31 | }; | ||
32 | struct memory_free_block | ||
33 | { | ||
34 | struct memory_free_block | ||
35 | *link; | ||
36 | }; | ||
37 | |||
38 | struct memory_cache | ||
39 | { | ||
40 | struct memory_cache | ||
41 | *less,*more,*same; | ||
42 | unsigned int | ||
43 | left; // number of free slabs | ||
44 | struct memory_slab | ||
45 | *used; | ||
46 | struct memory_slab | ||
47 | *free; | ||
48 | struct memory_slab | ||
49 | *reap; | ||
50 | unsigned int | ||
51 | size,original_size; | ||
52 | unsigned int | ||
53 | page_size; | ||
54 | unsigned int | ||
55 | blocks_per_slab; | ||
56 | int | ||
57 | page_order; | ||
58 | unsigned int | ||
59 | flags; | ||
60 | }; | ||
61 | |||
62 | struct memory_slab | ||
63 | { | ||
64 | struct memory_slab | ||
65 | *less,*more; | ||
66 | unsigned int // left == number of free blocks left | ||
67 | left; | ||
68 | struct memory_free_block | ||
69 | *free; | ||
70 | }; | ||
71 | |||
72 | #endif \ No newline at end of file | ||