source: git/omalloc/omBin.c @ 91c4012

/*******************************************************************
 *  File:    omBin.c
 *  Purpose: definitions of routines for working with bins
 *  Author:  obachman (Olaf Bachmann)
 *  Created: 11/99
 *  Version: $Id: omBin.c,v 1.3 2000-08-14 12:26:40 obachman Exp $
 *******************************************************************/

#include "omAlloc.h"
/* this should go away */

#ifdef OM_INTERNAL_DEBUG
size_t omSizeOfBinAddr(void* addr)
{
  return _omSizeOfBinAddr(addr);
}
#endif

/*****************************************************************
 *
 * SpecBin business
 *
 *****************************************************************/
#define om_LargeBin ((omBin) 1)
omBin _omGetSpecBin(size_t size, int align, int track)

{
  omBin om_new_specBin;
  long max_blocks;
  long sizeW;


  size = OM_ALIGN_SIZE(size);
#ifdef OM_ALIGNMENT_NEEDS_WORK
  if (align || size >= OM_SIZEOF_UNIQUE_MAX_BLOCK_THRESHOLD)
  {
    align = 1;
    size = OM_STRICT_ALIGN_SIZE(size);
  }
#else
  align = 0;
#endif  
  
  if (size > SIZEOF_OM_BIN_PAGE)
  {
    /* need page header */
    max_blocks = - (long) 
      ((size+(SIZEOF_SYSTEM_PAGE-SIZEOF_OM_BIN_PAGE))+SIZEOF_SYSTEM_PAGE-1)
      / SIZEOF_SYSTEM_PAGE;
    sizeW = ((-max_blocks*SIZEOF_SYSTEM_PAGE) - 
             (SIZEOF_SYSTEM_PAGE - SIZEOF_OM_BIN_PAGE)) / SIZEOF_LONG;
    om_new_specBin = om_LargeBin;
  }
  else
  {
    /* SIZEOF_OM_BIN_PAGE == max_blocks*size + r1; r1 < size */
    /* r1 = max_blocks*(size_padding) + r2; r2 < max_blocks */
    max_blocks = SIZEOF_OM_BIN_PAGE / size;
    sizeW = (SIZEOF_OM_BIN_PAGE % size) / max_blocks;
#ifdef OM_ALIGNMENT_NEEDS_WORK
    if (align)
      sizeW = ((size + sizeW) & ~ (SIZEOF_STRICT_ALIGNMENT - 1));
    else
#endif
      sizeW = ((size + sizeW) & ~ (SIZEOF_OM_ALIGNMENT - 1));
    
    omAssume(sizeW >= size);
    omAssume(max_blocks*sizeW <= SIZEOF_OM_BIN_PAGE);
    omAssume((max_blocks+1)*sizeW > SIZEOF_OM_BIN_PAGE ||
             max_blocks*(sizeW + SIZEOF_STRICT_ALIGNMENT) > SIZEOF_OM_BIN_PAGE);

    sizeW = sizeW >> LOG_SIZEOF_LONG;
    if (size > OM_MAX_BLOCK_SIZE)
    {
      om_new_specBin = om_LargeBin;
    }
#ifdef OM_ALIGNMENT_NEEDS_WORK
    else if (align)
    {
      om_new_specBin = omSmallSize2AlignedBin( size );
    }
#endif
#ifdef OM_HAVE_TRACK
    else if (track)
    {
      om_new_specBin = omSmallSize2TrackBin( size );
    }
#endif
    else 
    {
      om_new_specBin = omSmallSize2Bin( size );
    }
  }

  if (om_new_specBin == om_LargeBin ||
      om_new_specBin->max_blocks < max_blocks)
  {
    omSpecBin s_bin;
#ifdef OM_HAVE_TRACK
    if (track)
      s_bin = omFindInSortedGList(om_SpecTrackBin, next, max_blocks, max_blocks);
    else
#endif
      s_bin = omFindInSortedGList(om_SpecBin, next, max_blocks, max_blocks);

    if (s_bin != NULL) 
    {
      (s_bin->ref)++;
      omAssume(s_bin->bin != NULL && 
             s_bin->bin->max_blocks == s_bin->max_blocks &&
             s_bin->bin->sizeW == sizeW);
      return s_bin->bin;
    }
    s_bin = (omSpecBin) omAlloc(sizeof(omSpecBin_t));
    s_bin->ref = 1;
    s_bin->next = NULL;
    s_bin->max_blocks = max_blocks;
    s_bin->bin = (omBin) omAlloc(sizeof(omBin_t));
    s_bin->bin->current_page = om_ZeroPage;
    s_bin->bin->last_page = NULL;
    s_bin->bin->next = NULL;
    s_bin->bin->sizeW = sizeW;
    s_bin->bin->max_blocks = max_blocks;
    s_bin->bin->sticky = 0;
#ifdef OM_HAVE_TRACK
    if (track)
    {
      om_SpecTrackBin = omInsertInSortedGList(om_SpecTrackBin, next, max_blocks, s_bin);
    }
    else
#endif
      om_SpecBin = omInsertInSortedGList(om_SpecBin, next, max_blocks, s_bin);
    return s_bin->bin;
  }
  else
  {
    return om_new_specBin;
  }
}

void _omUnGetSpecBin(omBin *bin_p, int force)
{
  omBin bin = *bin_p;
  if (! omIsStaticBin(bin))
  {
#ifdef OM_HAVE_TRACK 
    int track_bin = 0;
#endif 
    omSpecBin s_bin;

#ifdef OM_HAVE_TRACK
    s_bin = omFindInGList(om_SpecTrackBin, next, bin, bin);
    if (s_bin != NULL)
      track_bin = 1;
    else
#endif
        s_bin = omFindInSortedGList(om_SpecBin, next, max_blocks, bin->max_blocks);
        
    omAssume(s_bin != NULL);
    if (s_bin != NULL)
    {
      (s_bin->ref)--;
      if (s_bin->ref == 0 || force)
      {
        if(s_bin->bin->last_page == NULL || force)
        {
#ifdef OM_HAVE_TRACK
          if (track_bin)
            om_SpecTrackBin = omRemoveFromSortedGList(om_SpecTrackBin, next, max_blocks, s_bin);
          else
#endif
            om_SpecBin = omRemoveFromSortedGList(om_SpecBin, next, max_blocks, s_bin);
          omFreeSize(s_bin->bin, sizeof(omBin_t));
          omFreeSize(s_bin, sizeof(omSpecBin_t));
        }
      }
    }
  }
  *bin_p = NULL;
}

/*****************************************************************
 *
 * Statistics
 *
 *****************************************************************/
static void omGetBinStat(omBin bin, int *pages_p, int *used_blocks_p, 
                          int *free_blocks_p)
{
  int pages = 0, used_blocks = 0, free_blocks = 0;
  int where = 1;
  
  omBinPage page = bin->last_page;
  while (page != NULL)
  {
    pages++; if (where == 1) 
    {
      used_blocks += omGetUsedBlocksOfPage(page) + 1;
      if (bin->max_blocks > 0)
        free_blocks += bin->max_blocks - omGetUsedBlocksOfPage(page) -1;
    }
    else 
    {
      if (bin->max_blocks > 1)
        used_blocks += bin->max_blocks;
      else
        used_blocks++;
    }
    if (page == bin->current_page) where = -1;
    page = page->prev;
  }
  *pages_p = pages;
  *used_blocks_p = used_blocks;
  *free_blocks_p = free_blocks;
}

static void omGetTotalBinStat(omBin bin, int *pages_p, int *used_blocks_p, 
                               int *free_blocks_p)
{
  int t_pages = 0, t_used_blocks = 0, t_free_blocks = 0;
  int pages = 0, used_blocks = 0, free_blocks = 0;
 
  while (bin != NULL)
  {
    omGetBinStat(bin, &pages, &used_blocks, &free_blocks);
    t_pages += pages;
    t_used_blocks += used_blocks;
    t_free_blocks += free_blocks;
    bin = bin->next;
  }
  *pages_p = t_pages;
  *used_blocks_p = t_used_blocks;
  *free_blocks_p = t_free_blocks;
}

static void omPrintBinStat(FILE * fd, omBin bin, int track, int* pages, int* used_blocks, int* free_blocks)
{
  if (track)
  {
    fprintf(fd, "T \t \t");
  }
  else
  {
    fprintf(fd, "%s%u\t%ld\t", (omIsStaticNormalBin(bin) ? " " : (omIsTrackBin(bin) ? "T" : "*")),
            bin->sizeW, bin->max_blocks);
  }
  omGetTotalBinStat(bin, pages, used_blocks, free_blocks);
  fprintf(fd, "%d\t%d\t%d\n", *pages, *free_blocks, *used_blocks);
  if (bin->next != NULL)
  {
    int s_pages, s_free_blocks, s_used_blocks;
    while (bin != NULL)
    {
      omGetBinStat(bin, &s_pages, &s_used_blocks, &s_free_blocks);
      fprintf(fd, " \t \t%d\t%d\t%d\t%d\n", s_pages, s_free_blocks, s_used_blocks, 
              (int) bin->sticky);
      bin = bin->next;
      *pages += s_pages;
      *used_blocks += s_used_blocks;
      *free_blocks += s_free_blocks;
    }
  }
}
  
void omPrintBinStats(FILE* fd)
{
  int i = OM_MAX_BIN_INDEX, pages=0, used_blocks=0, free_blocks=0;
  int pages_p, used_blocks_p, free_blocks_p;
  omSpecBin s_bin = om_SpecBin;
  
  fprintf(fd, " SizeW\tBlocks\tUPages\tFBlocks\tUBlocks\tSticky\n");
  fflush(fd);
  while (s_bin != NULL || i >= 0)
  {
    if (s_bin == NULL || (i >= 0 && (unsigned long) om_StaticBin[i].max_blocks < (unsigned long) s_bin->bin->max_blocks))
    {
       omPrintBinStat(fd, &om_StaticBin[i], 0, &pages_p, &used_blocks_p, &free_blocks_p);
       pages += pages_p;
       used_blocks += used_blocks_p;
       free_blocks += free_blocks_p;
#ifdef OM_HAVE_TRACK
       if (om_StaticTrackBin[i].current_page != om_ZeroPage) 
       {
         omPrintBinStat(fd, &om_StaticTrackBin[i], 1, &pages_p, &used_blocks_p, &free_blocks_p);
         pages += pages_p;
         used_blocks += used_blocks_p;
         free_blocks += free_blocks_p;
       }
#endif       
       i--;
    }
    else
    {
      omPrintBinStat(fd, s_bin->bin,0, &pages_p, &used_blocks_p, &free_blocks_p);
      pages += pages_p;
      used_blocks += used_blocks_p;
      free_blocks += free_blocks_p;
      s_bin = s_bin->next;
    }
  }
#ifdef OM_HAVE_TRACK
  s_bin = om_SpecTrackBin;
  while (s_bin != NULL)
  {
    omPrintBinStat(fd, s_bin->bin, 0,  &pages_p, &used_blocks_p, &free_blocks_p);
    s_bin = s_bin->next;
    pages += pages_p;
    used_blocks += used_blocks_p;
    free_blocks += free_blocks_p;
  }
#endif
  fprintf(fd, "----------------------------------------\n");
  fprintf(fd, "      \t      \t%d\t%d\t%d\n", pages, free_blocks, used_blocks);
}
 
/*****************************************************************
 *
 * Sticky business
 *
 *****************************************************************/
#define omGetStickyBin(bin, sticky_tag) \
   omFindInGList(bin, next, sticky, sticky_tag)

static omBin omCreateStickyBin(omBin bin, unsigned long sticky)
{
  omBin s_bin = (omBin) omAlloc(sizeof(omBin_t));
  s_bin->sticky = sticky;
  s_bin->current_page = om_ZeroPage;
  s_bin->last_page = NULL;
  s_bin->max_blocks = bin->max_blocks;
  s_bin->sizeW = bin->sizeW;
  s_bin->next = bin->next;
  bin->next = s_bin;
  return s_bin;
}

unsigned long omGetMaxStickyBinTag(omBin bin)
{
  unsigned long sticky = 0;
  do
  {
    if (bin->sticky > sticky) sticky = bin->sticky;
    bin = bin->next;
  }
  while (bin != NULL);
  return sticky;
}

unsigned long omGetNewStickyBinTag(omBin bin)
{
  unsigned long sticky = omGetMaxStickyBinTag(bin);
  if (sticky < BIT_SIZEOF_LONG - 2)
  {
    sticky++;
    omCreateStickyBin(bin, sticky);
    return sticky;
  }
  else
  {
    omAssume(sticky == BIT_SIZEOF_LONG - 1);
  }
  return sticky;
}

void omSetStickyBinTag(omBin bin, unsigned long sticky_tag)
{
  omBin s_bin;
  s_bin = omGetStickyBin(bin, sticky_tag);
  
  if (s_bin != bin)
  {
    omBinPage tc, tl;
    unsigned long ts;
    
    if (s_bin == NULL) s_bin = omCreateStickyBin(bin, sticky_tag);
    ts = bin->sticky;
    tl = bin->last_page;
    tc = bin->current_page;
    bin->sticky = s_bin->sticky;
    bin->current_page = s_bin->current_page;
    bin->last_page = s_bin->last_page;
    s_bin->sticky = ts;
    s_bin->last_page = tl;
    s_bin->current_page = tc;
  }
}

void omUnSetStickyBinTag(omBin bin, unsigned long sticky)
{
  omAssume(omGetStickyBin(bin, 0) != NULL);
  if (bin->sticky == sticky)
    omSetStickyBinTag(bin, 0);
}

static void omMergeStickyPages(omBin to_bin, omBin from_bin)
{
#ifdef HAVE_OM_ASSUME
  int length = omGListLength(to_bin->last_page, prev) +
    omGListLength(from_bin->last_page, prev);
#endif  
  
  omBinPage page = from_bin->last_page;
  omAssume(to_bin->sticky == 0);
  omAssume(to_bin->sizeW == from_bin->sizeW);
  omAssume(to_bin != from_bin);
  omAssume(omIsOnGList(to_bin->next, next, from_bin) 
           || 
           omIsOnGList(from_bin->next, next, to_bin));

  if (page == NULL) return;
  do
  {
    omSetStickyOfPage(page, 0);
    if (page->prev == NULL) break;
    page = page->prev;
  }
  while(1);

  if (to_bin->last_page == NULL)
  {
    omAssume(to_bin->current_page == om_ZeroPage);
    to_bin->last_page = from_bin->last_page;
    to_bin->current_page = from_bin->current_page;
    return;
  }
  
  omAssume(to_bin->current_page != om_ZeroPage && 
           to_bin->current_page != NULL);

  if (to_bin->current_page->current != NULL)
  {
    if (to_bin->current_page->prev == NULL)
    {
      from_bin->last_page->next = to_bin->current_page;
      to_bin->current_page->prev = from_bin->last_page;
      to_bin->current_page = from_bin->current_page;
      return;
    }
    to_bin->current_page = to_bin->current_page->prev;
  }
  else
  {
    /* need to reset this here, since new current_page is going to be
       from_bin->current_page, and only for current_page may we have 
       used_blocks != 0 && current == NULL */
    to_bin->current_page->used_blocks = 0;
  }
  

  omAssume(to_bin->current_page != NULL && 
           to_bin->current_page->current == NULL &&
           to_bin->current_page->used_blocks == 0);

  from_bin->last_page->next = to_bin->current_page->next;
  if (to_bin->current_page->next != NULL) 
    to_bin->current_page->next->prev =  from_bin->last_page;
  else
  {
    omAssume(to_bin->current_page == to_bin->last_page);
    to_bin->last_page = from_bin->last_page;
  }
  to_bin->current_page->next = page;
  page->prev = to_bin->current_page;
  to_bin->current_page = from_bin->current_page;
  
#ifdef HAVE_OM_ASSUME
  omAssume(omGListLength(to_bin->last_page, prev) == length);
#endif
}

void omDeleteStickyBinTag(omBin bin, unsigned long sticky)
{
  omBin no_sticky_bin = NULL;
  omBin sticky_bin = NULL;

  if (sticky == 0)
  {
    omAssume(0);
    return;
  }
  
  sticky_bin = omGetStickyBin(bin, sticky);
  if (sticky_bin != NULL)
  {
    no_sticky_bin = omGetStickyBin(bin, 0);
    omAssume(no_sticky_bin != NULL && sticky_bin != no_sticky_bin);

    omMergeStickyPages(no_sticky_bin, sticky_bin);

    if (bin == sticky_bin) 
    {
      sticky_bin = no_sticky_bin;
      omSetStickyBinTag(bin, 0);
    }
    bin->next = omRemoveFromGList(bin->next, next, sticky_bin);
    omFreeSize(sticky_bin, sizeof(omBin_t));
  }
}


 
/*****************************************************************
*
* AllBin business
*
*****************************************************************/
unsigned long omGetNewStickyAllBinTag()
{
  unsigned long sticky = 0, new_sticky;
  int i;
  omSpecBin s_bin;
  // first, find new sticky tag
  for (i=0; i<=OM_MAX_BIN_INDEX; i++)
  {
    new_sticky = omGetMaxStickyBinTag(&(om_StaticBin[i]));
    if (new_sticky > sticky) sticky = new_sticky;
  }
  s_bin = om_SpecBin;
  while (s_bin != NULL) 
  {
    new_sticky = omGetMaxStickyBinTag(s_bin->bin);
    if (new_sticky > sticky) sticky = new_sticky;
    s_bin = s_bin->next;
  }
  if (sticky < BIT_SIZEOF_LONG - 2) 
  {
    sticky++;
    for (i=0; i<=OM_MAX_BIN_INDEX; i++)
    {
      omCreateStickyBin(&(om_StaticBin[i]), sticky);
    }
    s_bin = om_SpecBin;
    while (s_bin != NULL) 
    {
      omCreateStickyBin(s_bin->bin, sticky);
      s_bin = s_bin->next;
    }
    return sticky;
  }
  else
  {
    omBin bin;
    omAssume(sticky == BIT_SIZEOF_LONG - 1);
    for (i=0; i<=OM_MAX_BIN_INDEX; i++)
    {
      bin = &om_StaticBin[i];
      if (omGetStickyBin(bin, BIT_SIZEOF_LONG -1) == NULL)
        omCreateStickyBin(bin, BIT_SIZEOF_LONG -1);
    }
    s_bin = om_SpecBin;
    while (s_bin != NULL) 
    {
      if (omGetStickyBin(s_bin->bin, BIT_SIZEOF_LONG -1) == NULL)
        omCreateStickyBin(s_bin->bin, BIT_SIZEOF_LONG -1);
      s_bin = s_bin->next;
    }
    return BIT_SIZEOF_LONG - 1;
  }
}

void omSetStickyAllBinTag(unsigned long sticky)
{
  omSpecBin s_bin = om_SpecBin;
  int i;
  for (i=0; i<=OM_MAX_BIN_INDEX; i++)
  {
    omSetStickyBinTag(&(om_StaticBin[i]), sticky);
  }
  while (s_bin != NULL) 
  {
    omSetStickyBinTag(s_bin->bin, sticky);
    s_bin = s_bin->next;
  }
}

void omUnSetStickyAllBinTag(unsigned long sticky)
{
  omSpecBin s_bin = om_SpecBin;
  int i;
  for (i=0; i<=OM_MAX_BIN_INDEX; i++)
  {
    omUnSetStickyBinTag(&(om_StaticBin[i]), sticky);
  }
  while (s_bin != NULL) 
  {
    omUnSetStickyBinTag(s_bin->bin, sticky);
    s_bin = s_bin->next;
  }
}

void omDeleteStickyAllBinTag(unsigned long sticky)
{
  omSpecBin s_bin = om_SpecBin;
  int i;
  for (i=0; i<=OM_MAX_BIN_INDEX; i++)
  {
    omDeleteStickyBinTag(&(om_StaticBin[i]), sticky);
  }
  while (s_bin != NULL) 
  {
    omDeleteStickyBinTag(s_bin->bin, sticky);
    s_bin = s_bin->next;
  }
}

#if 0
void omPrintMissing(omBin bin)
{
  omBinPage page = bin->last_page;
  
  while (page != NULL)
  {
    void* addr = (void*) page + SIZEOF_OM_BIN_PAGE_HEADER;
    int i;
    
    for (i=0; i<bin->max_blocks; i++)
    {
      if (! omIsOnList(page->current, addr))
        printf("%d:%p\n", i, addr);
      addr += bin->sizeW*SIZEOF_LONG;
    }
    page = page->prev;
  }
}
#endif

static  int omGetUsedBytesOfBin(omBin bin)
{
  int pages = 0, used_blocks = 0, free_blocks = 0;
  omGetTotalBinStat(bin, &pages, &used_blocks, &free_blocks);
  return used_blocks*bin->sizeW*SIZEOF_LONG;
}

size_t omGetUsedBinBytes()
{
  int i = OM_MAX_BIN_INDEX;
  omSpecBin s_bin = om_SpecBin;
  size_t used = 0;
  
  for (; i>=0; i--)
  {
    used += omGetUsedBytesOfBin(&om_StaticBin[i]);
  }
  while (s_bin != NULL)
  {
    used += omGetUsedBytesOfBin(s_bin->bin);
    s_bin = s_bin->next;
  }
#ifdef OM_HAVE_TRACK
  for (i=OM_MAX_BIN_INDEX; i>=0; i--)
  {
    used += omGetUsedBytesOfBin(&om_StaticTrackBin[i]);
  }
  s_bin = om_SpecTrackBin;
  while (s_bin != NULL)
  {
    used += omGetUsedBytesOfBin(s_bin->bin);
    s_bin = s_bin->next;
  }
#endif

  return used;
}