1 | /******************************************************************* |
---|
2 | * File: omAlloc.c |
---|
3 | * Purpose: implementation of main omalloc functions |
---|
4 | * Author: obachman@mathematik.uni-kl.de (Olaf Bachmann) |
---|
5 | * Created: 11/99 |
---|
6 | *******************************************************************/ |
---|
7 | #ifndef OM_ALLOC_C |
---|
8 | #define OM_ALLOC_C |
---|
9 | |
---|
10 | #include <omalloc/omalloc.h> |
---|
11 | /******************************************************************* |
---|
12 | * |
---|
13 | * global variables |
---|
14 | * |
---|
15 | *******************************************************************/ |
---|
16 | |
---|
17 | omBinPage_t om_ZeroPage[] = {{0, NULL, NULL, NULL, NULL}}; |
---|
18 | omSpecBin om_SpecBin = NULL; |
---|
19 | |
---|
20 | #include <omalloc/omTables.inc> |
---|
21 | |
---|
22 | |
---|
23 | /******************************************************************* |
---|
24 | * |
---|
25 | * Local stuff |
---|
26 | * |
---|
27 | *******************************************************************/ |
---|
28 | |
---|
29 | /* Get new page and initialize */ |
---|
30 | static omBinPage omAllocNewBinPage(omBin bin) |
---|
31 | { |
---|
32 | omBinPage newpage; |
---|
33 | void* tmp; |
---|
34 | int i = 1; |
---|
35 | |
---|
36 | if (bin->max_blocks > 0) newpage = omAllocBinPage(); |
---|
37 | else newpage = omAllocBinPages(-bin->max_blocks); |
---|
38 | |
---|
39 | omAssume(omIsAddrPageAligned((void*) newpage)); |
---|
40 | |
---|
41 | omSetTopBinAndStickyOfPage(newpage, bin, bin->sticky); |
---|
42 | newpage->used_blocks = -1; |
---|
43 | newpage->current = (void*) (((char*)newpage) + SIZEOF_OM_BIN_PAGE_HEADER); |
---|
44 | tmp = newpage->current; |
---|
45 | while (i < bin->max_blocks) |
---|
46 | { |
---|
47 | tmp = *((void**)tmp) = ((void**) tmp) + bin->sizeW; |
---|
48 | i++; |
---|
49 | } |
---|
50 | *((void**)tmp) = NULL; |
---|
51 | omAssume(omListLength(newpage->current) == |
---|
52 | (bin->max_blocks > 1 ? bin->max_blocks : 1)); |
---|
53 | return newpage; |
---|
54 | } |
---|
55 | |
---|
56 | /* primitives for handling of list of pages */ |
---|
57 | OM_INLINE_LOCAL void omTakeOutBinPage(omBinPage page, omBin bin) |
---|
58 | { |
---|
59 | if (bin->current_page == page) |
---|
60 | { |
---|
61 | if (page->next == NULL) |
---|
62 | { |
---|
63 | if (page->prev == NULL) |
---|
64 | { |
---|
65 | omAssume(bin->last_page == page); |
---|
66 | bin->last_page = NULL; |
---|
67 | bin->current_page = om_ZeroPage; |
---|
68 | return; |
---|
69 | } |
---|
70 | bin->current_page = page->prev; |
---|
71 | } |
---|
72 | else |
---|
73 | bin->current_page = page->next; |
---|
74 | } |
---|
75 | if (bin->last_page == page) |
---|
76 | { |
---|
77 | omAssume(page->prev != NULL && page->next == NULL); |
---|
78 | bin->last_page = page->prev; |
---|
79 | } |
---|
80 | else |
---|
81 | { |
---|
82 | omAssume(page->next != NULL); |
---|
83 | page->next->prev = page->prev; |
---|
84 | } |
---|
85 | if (page->prev != NULL) page->prev->next = page->next; |
---|
86 | } |
---|
87 | |
---|
88 | OM_INLINE_LOCAL void omInsertBinPage(omBinPage after, omBinPage page, omBin bin) |
---|
89 | { |
---|
90 | if (bin->current_page == om_ZeroPage) |
---|
91 | { |
---|
92 | omAssume(bin->last_page == NULL); |
---|
93 | page->next = NULL; |
---|
94 | page->prev = NULL; |
---|
95 | bin->current_page = page; |
---|
96 | bin->last_page = page; |
---|
97 | } |
---|
98 | else |
---|
99 | { |
---|
100 | omAssume(after != NULL && bin->last_page != NULL); |
---|
101 | if (after == bin->last_page) |
---|
102 | { |
---|
103 | bin->last_page = page; |
---|
104 | } |
---|
105 | else |
---|
106 | { |
---|
107 | omAssume(after->next != NULL); |
---|
108 | after->next->prev = page; |
---|
109 | } |
---|
110 | page->next = after->next; |
---|
111 | after->next = page; |
---|
112 | page->prev = after; |
---|
113 | } |
---|
114 | } |
---|
115 | |
---|
116 | /* bin->current_page is empty, get new bin->current_page, return addr*/ |
---|
117 | void* omAllocBinFromFullPage(omBin bin) |
---|
118 | { |
---|
119 | void* addr; |
---|
120 | omBinPage newpage; |
---|
121 | omAssume(bin->current_page->current == NULL); |
---|
122 | |
---|
123 | if (bin->current_page != om_ZeroPage) |
---|
124 | { |
---|
125 | omAssume(bin->last_page != NULL); |
---|
126 | /* Set this to zero, but preserve the first bit, |
---|
127 | so that tracking works */ |
---|
128 | #ifdef OM_HAVE_TRACK |
---|
129 | bin->current_page->used_blocks &= (((unsigned long) 1) << (BIT_SIZEOF_LONG -1)); |
---|
130 | #else |
---|
131 | bin->current_page->used_blocks = 0; |
---|
132 | #endif |
---|
133 | } |
---|
134 | |
---|
135 | if (!bin->sticky && bin->current_page->next != NULL) |
---|
136 | { |
---|
137 | omAssume(bin->current_page->next->current != NULL); |
---|
138 | newpage = bin->current_page->next; |
---|
139 | } |
---|
140 | else |
---|
141 | { |
---|
142 | // need to Allocate new page |
---|
143 | newpage = omAllocNewBinPage(bin); |
---|
144 | omInsertBinPage(bin->current_page, newpage, bin); |
---|
145 | } |
---|
146 | |
---|
147 | bin->current_page = newpage; |
---|
148 | omAssume(newpage != NULL && newpage != om_ZeroPage && |
---|
149 | newpage->current != NULL); |
---|
150 | __omTypeAllocFromNonEmptyPage(void*, addr, newpage); |
---|
151 | return addr; |
---|
152 | } |
---|
153 | |
---|
154 | |
---|
155 | /* page->used_blocks <= 0, so, either free page or reallocate to |
---|
156 | the right of current_page */ |
---|
157 | /* |
---|
158 | * Now: there are three different strategies here, on what to do with |
---|
159 | * pages which were full and now have a free block: |
---|
160 | * 1.) Insert at the end (default) |
---|
161 | * 2.) Insert after current_page => #define PAGE_AFTER_CURRENT |
---|
162 | * 3.) Let it be new current_page => #define PAGE_BEFORE_CURRENT |
---|
163 | * Still need to try out which is best |
---|
164 | */ |
---|
165 | void omFreeToPageFault(omBinPage page, void* addr) |
---|
166 | { |
---|
167 | omBin bin; |
---|
168 | omAssume(page->used_blocks <= 0L); |
---|
169 | |
---|
170 | #ifdef OM_HAVE_TRACK |
---|
171 | if (page->used_blocks < 0L) |
---|
172 | { |
---|
173 | omFreeTrackAddr(addr); |
---|
174 | return; |
---|
175 | } |
---|
176 | #endif |
---|
177 | |
---|
178 | bin = omGetBinOfPage(page); |
---|
179 | if ((page->current != NULL) || (bin->max_blocks <= 1)) |
---|
180 | { |
---|
181 | // all blocks of page are now collected |
---|
182 | omTakeOutBinPage(page, bin); |
---|
183 | // page can be freed |
---|
184 | if (bin->max_blocks > 0) |
---|
185 | omFreeBinPage(page); |
---|
186 | else |
---|
187 | omFreeBinPages(page, - bin->max_blocks); |
---|
188 | #ifdef OM_HAVE_TRACK |
---|
189 | om_JustFreedPage = page; |
---|
190 | #endif |
---|
191 | } |
---|
192 | else |
---|
193 | { |
---|
194 | // page was full |
---|
195 | page->current = addr; |
---|
196 | page->used_blocks = bin->max_blocks - 2; |
---|
197 | *((void**)addr) = NULL; |
---|
198 | |
---|
199 | omTakeOutBinPage(page, bin); |
---|
200 | #if defined(PAGE_BEFORE_CURRENT) |
---|
201 | if (bin->current_page->prev != NULL) |
---|
202 | omInsertBinPage(bin->current_page->prev, page); |
---|
203 | else |
---|
204 | omInsertBinPage(bin->current_page, page, bin); |
---|
205 | bin->current_page = page; |
---|
206 | #else |
---|
207 | # if defined(PAGE_AFTER_CURRENT) |
---|
208 | omInsertBinPage(bin->current_page, page, bin); |
---|
209 | # else |
---|
210 | omInsertBinPage(bin->last_page, page, bin); |
---|
211 | # endif |
---|
212 | #endif |
---|
213 | } |
---|
214 | } |
---|
215 | |
---|
216 | /******************************************************************* |
---|
217 | * |
---|
218 | * DoRealloc |
---|
219 | * |
---|
220 | *******************************************************************/ |
---|
221 | #ifdef OM_ALIGNMNET_NEEDS_WORK |
---|
222 | #define DO_ZERO(flag) (flag & 1) |
---|
223 | #else |
---|
224 | #define DO_ZERO(flag) flag |
---|
225 | #endif |
---|
226 | |
---|
227 | void* omDoRealloc(void* old_addr, size_t new_size, int flag) |
---|
228 | { |
---|
229 | void* new_addr; |
---|
230 | |
---|
231 | if (!omIsBinPageAddr(old_addr) && new_size > OM_MAX_BLOCK_SIZE) |
---|
232 | { |
---|
233 | if (DO_ZERO(flag)) |
---|
234 | return omRealloc0Large(old_addr, new_size); |
---|
235 | else |
---|
236 | return omReallocLarge(old_addr, new_size); |
---|
237 | } |
---|
238 | else |
---|
239 | { |
---|
240 | size_t old_size = omSizeOfAddr(old_addr); |
---|
241 | size_t min_size; |
---|
242 | |
---|
243 | omAssume(OM_IS_ALIGNED(old_addr)); |
---|
244 | |
---|
245 | #ifdef OM_ALIGNMENT_NEEDS_WORK |
---|
246 | if (flag & 2) |
---|
247 | __omTypeAllocAligned(void*, new_addr, new_size); |
---|
248 | else |
---|
249 | #endif |
---|
250 | __omTypeAlloc(void*, new_addr, new_size); |
---|
251 | |
---|
252 | new_size = omSizeOfAddr(new_addr); |
---|
253 | min_size = (old_size < new_size ? old_size : new_size); |
---|
254 | omMemcpyW(new_addr, old_addr, min_size >> LOG_SIZEOF_LONG); |
---|
255 | |
---|
256 | if (DO_ZERO(flag) && (new_size > old_size)) |
---|
257 | omMemsetW((char*) new_addr + min_size, 0, (new_size - old_size) >> LOG_SIZEOF_LONG); |
---|
258 | |
---|
259 | __omFreeSize(old_addr, old_size); |
---|
260 | |
---|
261 | return new_addr; |
---|
262 | } |
---|
263 | } |
---|
264 | #endif /* OM_ALLOC_C */ |
---|