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