source: git/omalloc/omBinPage.c @ 8d1432e

spielwiese
Last change on this file since 8d1432e was c4ea0bb, checked in by Hans Schoenemann <hannes@…>, 8 years ago
omalloc: opt.
  • Property mode set to 100644
File size: 17.8 KB
Line 
1/*******************************************************************
2 *  File:    omBinPage.c
3 *  Purpose: implementation of routines for primitve BinPage managment
4 *  Author:  obachman (Olaf Bachmann)
5 *  Created: 11/99
6 *******************************************************************/
7#include <mylimits.h>
8#include "omalloc.h"
9#include "omDefaultConfig.h"
10
11/*******************************************************************
12 *
13 * Local declarations
14 *
15 *******************************************************************/
16
17/* define if you want to keep regions approximately in order */
18#define OM_KEEP_REGIONS_ORDER
19
20struct omBinPageRegion_s
21{
22  void* current;        /* linked list of free pages */
23  omBinPageRegion next; /* nex/prev pointer in ring of regions */
24  omBinPageRegion prev;
25  char* init_addr;      /* pointer portion of inital chunk which is still free */
26  char* addr;         /* addr returned by alloc */
27  int   init_pages;   /* number of pages still available in init_chunk */
28  int   used_pages;     /* number of used pages */
29  int pages;          /* total size of region */
30};
31
32/* globale variable holding pointing int regions ring */
33static omBinPageRegion om_CurrentBinPageRegion = NULL;
34unsigned long om_MaxBinPageIndex = 0;
35unsigned long om_MinBinPageIndex = ULONG_MAX;
36unsigned long *om_BinPageIndicies = NULL;
37
38/* declaration of local procs */
39static void* omTakeOutConsecutivePages(omBinPageRegion region, int how_many);
40static omBinPageRegion omAllocNewBinPagesRegion(int min_pages);
41static void omFreeBinPagesRegion(omBinPageRegion region);
42
43static void omBinPageIndexFault(unsigned long low_index, unsigned long high_index);
44static void omRegisterBinPages(void* low_addr, int pages);
45static void omUnregisterBinPages(void* low_addr, int pages);
46
47OM_INLINE_LOCAL void omTakeOutRegion(omBinPageRegion region)
48{
49  omAssume(region != NULL);
50
51  if (region->prev != NULL)
52  {
53    omAssume(region->prev != region && region->prev != region->next);
54    region->prev->next = region->next;
55  }
56
57  if (region->next != NULL)
58  {
59    omAssume(region->next != region && region->prev != region->next);
60    region->next->prev = region->prev;
61  }
62}
63
64OM_INLINE_LOCAL void omInsertRegionAfter(omBinPageRegion insert, omBinPageRegion after)
65{
66  omAssume(insert != NULL && after != NULL && insert != after);
67  insert->next = after->next;
68  insert->prev = after;
69  after->next = insert;
70  if (insert->next != NULL)
71  {
72    omAssume(insert->next != insert && insert->next != after);
73    insert->next->prev = insert;
74  }
75}
76
77OM_INLINE_LOCAL void omInsertRegionBefore(omBinPageRegion insert, omBinPageRegion before)
78{
79  omAssume(insert != NULL && before != NULL && insert != before);
80  insert->prev = before->prev;
81  insert->next = before;
82  before->prev = insert;
83  if (insert->prev != NULL)
84    insert->prev->next = insert;
85}
86
87
88/*******************************************************************
89 *
90 * Alloc/Free of BinPages
91 *
92 *******************************************************************/
93#define NEXT_PAGE(page) *((void**) page)
94#define OM_IS_EMPTY_REGION(region) ((region)->current == NULL && (region->init_addr == NULL))
95
96omBinPage omAllocBinPage()
97{
98  omBinPage bin_page;
99
100  if (om_CurrentBinPageRegion == NULL)
101    om_CurrentBinPageRegion = omAllocNewBinPagesRegion(1);
102
103  while (1)
104  {
105    if (om_CurrentBinPageRegion->current != NULL)
106    {
107      bin_page = om_CurrentBinPageRegion->current;
108      om_CurrentBinPageRegion->current = NEXT_PAGE(bin_page);
109      goto Found;
110    }
111    if (om_CurrentBinPageRegion->init_pages > 0)
112    {
113      bin_page = (omBinPage)om_CurrentBinPageRegion->init_addr;
114      om_CurrentBinPageRegion->init_pages--;
115      if (om_CurrentBinPageRegion->init_pages > 0)
116        om_CurrentBinPageRegion->init_addr += SIZEOF_SYSTEM_PAGE;
117      else
118        om_CurrentBinPageRegion->init_addr = NULL;
119      goto Found;
120    }
121    if (om_CurrentBinPageRegion->next != NULL)
122    {
123      om_CurrentBinPageRegion = om_CurrentBinPageRegion->next;
124    }
125    else
126    {
127      omBinPageRegion new_region = omAllocNewBinPagesRegion(1);
128      new_region->prev = om_CurrentBinPageRegion;
129      om_CurrentBinPageRegion->next = new_region;
130      om_CurrentBinPageRegion = new_region;
131    }
132  }
133
134  Found:
135  bin_page->region = om_CurrentBinPageRegion;
136  om_CurrentBinPageRegion->used_pages++;
137
138  om_Info.UsedPages++;
139  om_Info.AvailPages--;
140  if (om_Info.UsedPages > om_Info.MaxPages)
141    om_Info.MaxPages = om_Info.UsedPages;
142
143  OM_ALLOC_BINPAGE_HOOK;
144  return bin_page;
145}
146
147omBinPage omAllocBinPages(int how_many)
148{
149  omBinPage bin_page;
150  omBinPageRegion region;
151
152  if (om_CurrentBinPageRegion == NULL)
153    om_CurrentBinPageRegion = omAllocNewBinPagesRegion(how_many);
154
155  region = om_CurrentBinPageRegion;
156  while (1)
157  {
158    if (region->init_pages >= how_many)
159    {
160      bin_page = (omBinPage)region->init_addr;
161      region->init_pages -= how_many;
162      if (region->init_pages)
163        region->init_addr += how_many*SIZEOF_SYSTEM_PAGE;
164      else
165        region->init_addr = NULL;
166      goto Found;
167    }
168    if ((bin_page = omTakeOutConsecutivePages(region, how_many)) != NULL)
169    {
170      goto Found;
171    }
172    if (region->next != NULL)
173    {
174      region = region->next;
175    }
176    else
177    {
178      omBinPageRegion new_region = omAllocNewBinPagesRegion(how_many);
179      region->next = new_region;
180      new_region->prev = region;
181      region = new_region;
182    }
183  }
184  /*while (1) */
185
186  Found:
187  bin_page->region = region;
188  region->used_pages += how_many;
189
190  if (region != om_CurrentBinPageRegion && OM_IS_EMPTY_REGION(region))
191  {
192    omTakeOutRegion(region);
193    omInsertRegionBefore(region, om_CurrentBinPageRegion);
194  }
195  om_Info.UsedPages += how_many;
196  om_Info.AvailPages -= how_many;
197  if (om_Info.UsedPages > om_Info.MaxPages)
198    om_Info.MaxPages = om_Info.UsedPages;
199
200  OM_ALLOC_BINPAGE_HOOK;
201  return bin_page;
202}
203
204void omFreeBinPages(omBinPage bin_page, int how_many)
205{
206  omBinPageRegion region = bin_page->region;
207
208  region->used_pages -= how_many;
209  if (region->used_pages == 0)
210  {
211    if (region == om_CurrentBinPageRegion)
212    {
213      if (region->next != NULL)
214        om_CurrentBinPageRegion = region->next;
215      else
216        om_CurrentBinPageRegion = region->prev;
217    }
218    omTakeOutRegion(region);
219    omFreeBinPagesRegion(region);
220  }
221  else
222  {
223    if (region != om_CurrentBinPageRegion && OM_IS_EMPTY_REGION(region))
224    {
225      omTakeOutRegion(region);
226      omInsertRegionAfter(region, om_CurrentBinPageRegion);
227    }
228    if (how_many > 1)
229    {
230      int i = how_many;
231      char* page = (char *)bin_page;
232
233      while (i > 1)
234      {
235        NEXT_PAGE(page) = page + SIZEOF_SYSTEM_PAGE;
236        page = NEXT_PAGE(page);
237        i--;
238      }
239      NEXT_PAGE(page) = region->current;
240    }
241    else
242    {
243      NEXT_PAGE(bin_page) = region->current;
244    }
245    region->current = (void*) bin_page;
246  }
247  om_Info.AvailPages += how_many;
248  om_Info.UsedPages -= how_many;
249  OM_FREE_BINPAGE_HOOK;
250}
251
252static void* omTakeOutConsecutivePages(omBinPageRegion region, int pages)
253{
254  void* current;
255  char* iter;
256  void* prev = NULL;
257  void* bin_page;
258  int found;
259  current = region->current;
260  while (current != NULL)
261  {
262    found = 1;
263    iter = current;
264    while (NEXT_PAGE(iter) == (iter + SIZEOF_SYSTEM_PAGE))
265    {
266      iter = NEXT_PAGE(iter);
267      /* handle pathological case that iter + SIZEOF_SYSTEM_PAGE == 0 */
268      if (iter == NULL) return NULL;
269      found++;
270      if (found == pages)
271      {
272        bin_page = current;
273        if (current == region->current)
274        {
275          region->current = NEXT_PAGE(iter);
276        }
277        else
278        {
279          omAssume(prev != NULL);
280          NEXT_PAGE(prev) = NEXT_PAGE(iter);
281        }
282        return bin_page;
283      }
284    }
285    prev = iter;
286    current = NEXT_PAGE(iter);
287  }
288  return NULL;
289}
290
291/* Alloc a new region and insert into regions ring, set current to new region */
292static omBinPageRegion omAllocNewBinPagesRegion(int min_pages)
293{
294  omBinPageRegion region = omAllocFromSystem(sizeof(omBinPageRegion_t));
295  om_Info.InternalUsedBytesMalloc+=sizeof(omBinPageRegion_t);
296  void* addr;
297  int pages = (min_pages>om_Opts.PagesPerRegion ? min_pages : om_Opts.PagesPerRegion);
298  size_t size = pages*SIZEOF_SYSTEM_PAGE;
299
300  addr = _omVallocFromSystem(size, 1);
301  if (addr == NULL)
302  {
303    pages = min_pages;
304    size = min_pages*SIZEOF_SYSTEM_PAGE;
305    addr = omVallocFromSystem(size);
306  }
307
308  omRegisterBinPages(addr, pages);
309  region->addr = addr;
310  region->pages = pages;
311  region->used_pages = 0;
312  region->init_addr = addr;
313  region->init_pages = pages;
314  region->current = NULL;
315  region->next = NULL;
316  region->prev = NULL;
317
318  om_Info.AvailPages += pages;
319
320  om_Info.CurrentRegionsAlloc++;
321  if (om_Info.CurrentRegionsAlloc > om_Info.MaxRegionsAlloc)
322    om_Info.MaxRegionsAlloc = om_Info.CurrentRegionsAlloc;
323
324  return region;
325}
326
327/* Free region */
328static void omFreeBinPagesRegion(omBinPageRegion region)
329{
330  omAssume(region != NULL && region->used_pages == 0);
331
332  om_Info.AvailPages -= region->pages;
333  om_Info.CurrentRegionsAlloc--;
334
335  omUnregisterBinPages(region->addr, region->pages);
336  omVfreeToSystem(region->addr, region->pages*SIZEOF_SYSTEM_PAGE);
337  omFreeSizeToSystem(region, sizeof(omBinPageRegion_t));
338  om_Info.InternalUsedBytesMalloc-=sizeof(omBinPageRegion_t);
339}
340
341/*******************************************************************
342 *
343 * BinPage registration
344 *
345 *******************************************************************/
346
347static void omBinPageIndexFault(unsigned long low_index, unsigned long high_index)
348{
349  unsigned long index_diff = high_index - low_index;
350  omAssume(low_index <= high_index &&
351           (high_index > om_MaxBinPageIndex || low_index < om_MinBinPageIndex));
352
353  if (om_BinPageIndicies == NULL)
354  {
355    unsigned long i;
356    om_BinPageIndicies = (unsigned long*) omAllocFromSystem((index_diff + 1)*SIZEOF_LONG);
357    om_Info.InternalUsedBytesMalloc+=(index_diff + 1)*SIZEOF_LONG;
358    om_MaxBinPageIndex = high_index;
359    om_MinBinPageIndex = low_index;
360    for (i=0; i<=index_diff; i++) om_BinPageIndicies[i] = 0;
361  }
362  else
363  {
364    unsigned long old_length = om_MaxBinPageIndex - om_MinBinPageIndex + 1;
365    unsigned long new_length = (low_index < om_MinBinPageIndex ?
366                                om_MaxBinPageIndex - low_index :
367                                high_index - om_MinBinPageIndex) + 1;
368    om_BinPageIndicies  = (unsigned long*) omReallocSizeFromSystem(om_BinPageIndicies, old_length*SIZEOF_LONG,
369                                                                   new_length*SIZEOF_LONG);
370    om_Info.InternalUsedBytesMalloc+= (new_length-old_length)*SIZEOF_LONG;
371    if (low_index < om_MinBinPageIndex)
372    {
373      long i;
374      unsigned long offset = new_length - old_length;
375      for (i=old_length - 1; i >= 0; i--) om_BinPageIndicies[i+offset] = om_BinPageIndicies[i];
376      for (i=offset-1; i>=0; i--)  om_BinPageIndicies[i] = 0;
377      om_MinBinPageIndex = low_index;
378    }
379    else
380    {
381      unsigned long i;
382      for (i=old_length; i<new_length; i++) om_BinPageIndicies[i] = 0;
383      om_MaxBinPageIndex = high_index;
384    }
385  }
386}
387
388static void omRegisterBinPages(void* low_addr, int pages)
389{
390  unsigned long low_index = omGetPageIndexOfAddr(low_addr);
391  char* high_addr = (char *)low_addr + (pages-1)*SIZEOF_SYSTEM_PAGE;
392  unsigned long high_index = omGetPageIndexOfAddr(high_addr);
393  unsigned long shift;
394
395  if (low_index < om_MinBinPageIndex || high_index > om_MaxBinPageIndex)
396    omBinPageIndexFault(low_index, high_index);
397
398  shift = omGetPageShiftOfAddr(low_addr);
399  if (low_index < high_index)
400  {
401    if (shift == 0)
402    {
403      om_BinPageIndicies[low_index-om_MinBinPageIndex] = ULONG_MAX;
404    }
405    else
406    {
407      om_BinPageIndicies[low_index-om_MinBinPageIndex] |= ~ ((((unsigned long) 1) << shift) - 1);
408    }
409    for (shift = low_index+1; shift < high_index; shift++)
410    {
411      om_BinPageIndicies[shift-om_MinBinPageIndex] = ULONG_MAX;
412    }
413    shift = omGetPageShiftOfAddr(high_addr);
414    if (shift == BIT_SIZEOF_LONG - 1)
415    {
416      om_BinPageIndicies[high_index - om_MinBinPageIndex] = ULONG_MAX;
417    }
418    else
419    {
420      om_BinPageIndicies[high_index-om_MinBinPageIndex] |= ((((unsigned long) 1) << (shift + 1)) - 1);
421    }
422  }
423  else
424  {
425    high_index = omGetPageShiftOfAddr(high_addr);
426    while (high_index > shift)
427    {
428      om_BinPageIndicies[low_index-om_MinBinPageIndex] |= (((unsigned long) 1) << high_index);
429      high_index--;
430    }
431    om_BinPageIndicies[low_index-om_MinBinPageIndex] |= (((unsigned long) 1) << shift);
432  }
433}
434
435static void omUnregisterBinPages(void* low_addr, int pages)
436{
437  unsigned long low_index = omGetPageIndexOfAddr(low_addr);
438  char* high_addr = (char *)low_addr + (pages-1)*SIZEOF_SYSTEM_PAGE;
439  unsigned long high_index = omGetPageIndexOfAddr(high_addr);
440  unsigned long shift;
441
442  shift = omGetPageShiftOfAddr(low_addr);
443  if (low_index < high_index)
444  {
445    if (shift == 0)
446    {
447      om_BinPageIndicies[low_index-om_MinBinPageIndex] = 0;
448    }
449    else
450    {
451      om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ((((unsigned long) 1) << shift) - 1);
452    }
453    for (shift = low_index+1; shift < high_index; shift++)
454    {
455      om_BinPageIndicies[shift-om_MinBinPageIndex] = 0;
456    }
457    shift = omGetPageShiftOfAddr(high_addr);
458    if (shift == BIT_SIZEOF_LONG - 1)
459    {
460      om_BinPageIndicies[high_index - om_MinBinPageIndex] = 0;
461    }
462    else
463    {
464      om_BinPageIndicies[high_index-om_MinBinPageIndex] &= ~ ((((unsigned long) 1) << (shift + 1)) - 1);
465    }
466  }
467  else
468  {
469     high_index = omGetPageShiftOfAddr(high_addr);
470     while (high_index > shift)
471     {
472       om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ~(((unsigned long) 1) << high_index);
473       high_index--;
474     }
475     om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ~(((unsigned long) 1) << shift);
476  }
477}
478
479/***********************************************************************
480 *
481 * checking routines
482 *
483 *******************************************************************/
484#ifndef OM_NDEBUG
485#include "omDebug.h"
486
487int omIsKnownMemoryRegion(omBinPageRegion region)
488{
489  omBinPageRegion iter = om_CurrentBinPageRegion;
490
491  if (region == NULL || iter == NULL) return 0;
492  iter = omGListLast(om_CurrentBinPageRegion, prev);
493  do
494  {
495    if (region == iter) return 1;
496    iter = iter->next;
497  }
498  while (iter != NULL);
499  return 0;
500}
501
502
503omError_t omCheckBinPageRegion(omBinPageRegion region, int level, omError_t report, OM_FLR_DECL)
504{
505  if (level <= 0) return omError_NoError;
506
507  omCheckReturn(omCheckPtr(region, report, OM_FLR_VAL));
508  omCheckReturnCorrupted(! omIsKnownMemoryRegion(region));
509  omCheckReturnCorrupted(! omIsAddrPageAligned(region->addr) || ! omIsAddrPageAligned(region->current));
510  omCheckReturnCorrupted(region->used_pages < 0);
511  omCheckReturnCorrupted(region->init_pages < 0 || region->init_pages > region->pages);
512
513  if (region->init_pages)
514  {
515    omCheckReturnCorrupted(! omIsAddrPageAligned(region->init_addr));
516    omCheckReturnCorrupted(! (region->init_addr >= region->addr
517                              && region->init_addr <= region->addr + (region->pages -1)*SIZEOF_SYSTEM_PAGE));
518    omCheckReturnCorrupted(region->init_addr !=
519                           region->addr + (region->pages - region->init_pages)*SIZEOF_SYSTEM_PAGE);
520  }
521
522  omCheckReturn(omCheckList(region->current, level, report, OM_FLR_VAL));
523  omCheckReturnCorrupted(region->current == NULL && region->used_pages + region->init_pages != region->pages);
524  omCheckReturnCorrupted(level > 1 &&
525                         omListLength(region->current)+region->used_pages+region->init_pages != region->pages);
526  return omError_NoError;
527}
528
529omError_t omCheckBinPageRegions(int level, omError_t report, OM_FLR_DECL)
530{
531  omBinPageRegion iter = om_CurrentBinPageRegion;
532
533  if (level <= 0) return omError_NoError;
534  if (iter == NULL) return omError_NoError;
535
536  omCheckReturnError(om_CurrentBinPageRegion->next != NULL && OM_IS_EMPTY_REGION(om_CurrentBinPageRegion->next),
537                     omError_InternalBug);
538  omCheckReturnError(om_CurrentBinPageRegion->prev != NULL && ! OM_IS_EMPTY_REGION(om_CurrentBinPageRegion->prev),
539                     omError_InternalBug);
540
541
542  if (level > 1)
543  {
544    omBinPageRegion prev_last = (omBinPageRegion) omGListLast(om_CurrentBinPageRegion, prev);
545    omBinPageRegion next_last = (omBinPageRegion) omGListLast(om_CurrentBinPageRegion, next);
546
547    omCheckReturn(omCheckGList(iter, next, level, report, OM_FLR_VAL));
548    omCheckReturn(omCheckGList(iter, prev, level, report, OM_FLR_VAL));
549
550    omCheckReturnCorrupted(omGListLength(prev_last, next)
551                          !=
552                          omGListLength(next_last, prev));
553
554    omCheckReturn(omCheckBinPageRegion(om_CurrentBinPageRegion, level - 1, report, OM_FLR_VAL));
555
556    iter = om_CurrentBinPageRegion->next;
557    while (iter)
558    {
559      omCheckReturnError(OM_IS_EMPTY_REGION(iter), omError_InternalBug);
560
561      omCheckReturn(omCheckBinPageRegion(iter, level - 1, report, OM_FLR_VAL));
562      iter = iter->next;
563    }
564
565    iter = om_CurrentBinPageRegion->prev;
566    while (iter)
567    {
568      omCheckReturnError( !OM_IS_EMPTY_REGION(iter), omError_InternalBug);
569      omCheckReturn(omCheckBinPageRegion(iter, level - 1, report, OM_FLR_VAL));
570      iter = iter->prev;
571    }
572  }
573  return omError_NoError;
574}
575
576omBinPageRegion omFindRegionOfAddr(void* addr)
577{
578  omBinPageRegion region = om_CurrentBinPageRegion;
579
580  if (region == NULL) return 0;
581  region = omGListLast(region, prev);
582  do
583  {
584    if ((char *)addr >= region->addr
585    && (char *)addr < region->addr + (region->pages)*SIZEOF_SYSTEM_PAGE)
586      return region;
587    region = region->next;
588  }
589  while (region != NULL);
590  return NULL;
591}
592
593int omIsAddrOnFreeBinPage(void* addr)
594{
595  char *c_addr=(char *)addr;
596  omBinPageRegion region = om_CurrentBinPageRegion;
597
598  if (region == NULL) return 0;
599  do
600  {
601    if (c_addr > region->addr && c_addr < region->addr + (region->pages)*SIZEOF_SYSTEM_PAGE)
602    {
603      if (omIsOnList(region->current, omGetPageOfAddr(addr))) return 1;
604      return 0;
605    }
606    region = region->next;
607  }
608  while (region != NULL);
609  return 0;
610}
611
612#endif /* ! OM_NDEBUG */
Note: See TracBrowser for help on using the repository browser.