erl_goodfit_alloc.c

OTP是开放电信平台的简称

/* ``The contents of this file are subject to the Erlang Public License,
 * Version 1.1, (the "License"); you may not use this file except in
 * compliance with the License. You should have received a copy of the
 * Erlang Public License along with this software. If not, it can be
 * retrieved via the world wide web at http://www.erlang.org/.
 * 
 * Software distributed under the License is distributed on an "AS IS"
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
 * the License for the specific language governing rights and limitations
 * under the License.
 * 
 * The Initial Developer of the Original Code is Ericsson Utvecklings AB.
 * Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings
 * AB. All Rights Reserved.''
 * 
 *     $Id$
 */


/*
 * Description:	A "good fit" allocator. Segregated free-lists with a
 *              maximum search depth are used in order to find a good
 *              fit fast. Each free-list contains blocks of sizes in a
 *              specific range. First the free-list
 *              covering the desired size is searched if it is not empty.
 *              This search is stopped when the maximum search depth has
 *              been reached. If no free block was found in the free-list
 *              covering the desired size, the next non-empty free-list
 *              covering larger sizes is searched. The maximum search
 *              depth is by default 3. The insert and delete operations
 *              are O(1) and the search operation is O(n) where n is the
 *              maximum search depth, i.e. by default the all operations
 *              are O(1).
 *
 *              This module is a callback-module for erl_alloc_util.c
 *
 * Author: 	Rickard Green
 */

#ifdef HAVE_CONFIG_H
#  include "config.h"
#endif
#include "global.h"
#define GET_ERL_GF_ALLOC_IMPL
#include "erl_goodfit_alloc.h"

#define MIN_MBC_SZ			(16*1024)
#define MIN_MBC_FIRST_FREE_SZ		(4*1024)

#define MAX_SUB_MASK_IX \
  ((((Uint)1) << (NO_OF_BKT_IX_BITS - SUB_MASK_IX_SHIFT)) - 1)
#define MAX_SUB_BKT_IX ((((Uint)1) << SUB_MASK_IX_SHIFT) - 1)
#define MAX_BKT_IX (NO_OF_BKTS - 1)

#define MIN_BLK_SZ  UNIT_CEILING(sizeof(GFFreeBlock_t) + sizeof(Uint))

#define IX2SBIX(IX) ((IX) & (~(~((Uint)0) << SUB_MASK_IX_SHIFT)))
#define IX2SMIX(IX) ((IX) >> SUB_MASK_IX_SHIFT)
#define MAKE_BKT_IX(SMIX, SBIX)	\
  ((((Uint)(SMIX)) << SUB_MASK_IX_SHIFT) | ((Uint)(SBIX)))

#define SET_BKT_MASK_IX(BM, IX)						\
do {									\
    int sub_mask_ix__ = IX2SMIX((IX));					\
    (BM).main |= (((Uint) 1) << sub_mask_ix__);				\
    (BM).sub[sub_mask_ix__] |= (((Uint)1) << IX2SBIX((IX)));		\
} while (0)

#define UNSET_BKT_MASK_IX(BM, IX)					\
do {									\
    int sub_mask_ix__ = IX2SMIX((IX));					\
    (BM).sub[sub_mask_ix__] &= ~(((Uint)1) << IX2SBIX((IX)));		\
    if (!(BM).sub[sub_mask_ix__])					\
	(BM).main &= ~(((Uint)1) << sub_mask_ix__);			\
} while (0)

/* Buckets ... */

#define BKT_INTRVL_A		(1*sizeof(Unit_t))
#define BKT_INTRVL_B		(16*sizeof(Unit_t))
#define BKT_INTRVL_C		(96*sizeof(Unit_t))

#define BKT_MIN_SIZE_A		MIN_BLK_SZ
#define BKT_MIN_SIZE_B		(BKT_MAX_SIZE_A + 1)
#define BKT_MIN_SIZE_C		(BKT_MAX_SIZE_B + 1)
#define BKT_MIN_SIZE_D		(BKT_MAX_SIZE_C + 1)

#define BKT_MAX_SIZE_A		((NO_OF_BKTS/4)*BKT_INTRVL_A+BKT_MIN_SIZE_A-1)
#define BKT_MAX_SIZE_B		((NO_OF_BKTS/4)*BKT_INTRVL_B+BKT_MIN_SIZE_B-1)
#define BKT_MAX_SIZE_C		((NO_OF_BKTS/4)*BKT_INTRVL_C+BKT_MIN_SIZE_C-1)


#define BKT_MAX_IX_A		((NO_OF_BKTS*1)/4 - 1)
#define BKT_MAX_IX_B		((NO_OF_BKTS*2)/4 - 1)
#define BKT_MAX_IX_C		((NO_OF_BKTS*3)/4 - 1)
#define BKT_MAX_IX_D		((NO_OF_BKTS*4)/4 - 1)

#define BKT_MIN_IX_A		(0)
#define BKT_MIN_IX_B		(BKT_MAX_IX_A + 1)
#define BKT_MIN_IX_C		(BKT_MAX_IX_B + 1)
#define BKT_MIN_IX_D		(BKT_MAX_IX_C + 1)


#define BKT_IX_(BAP, SZ)						\
  ((SZ) <= BKT_MAX_SIZE_A						\
   ? (((SZ) - BKT_MIN_SIZE_A)/BKT_INTRVL_A + BKT_MIN_IX_A)		\
   : ((SZ) <= BKT_MAX_SIZE_B						\
      ? (((SZ) - BKT_MIN_SIZE_B)/BKT_INTRVL_B + BKT_MIN_IX_B)		\
      : ((SZ) <= BKT_MAX_SIZE_C						\
	 ? (((SZ) - BKT_MIN_SIZE_C)/BKT_INTRVL_C + BKT_MIN_IX_C)	\
	 : ((SZ) <= (BAP)->bkt_max_size_d				\
	    ? (((SZ) - BKT_MIN_SIZE_D)/(BAP)->bkt_intrvl_d + BKT_MIN_IX_D)\
	    : (NO_OF_BKTS - 1)))))

#define BKT_MIN_SZ_(BAP, IX)						\
  ((IX) <= BKT_MAX_IX_A							\
   ? (((IX) - BKT_MIN_IX_A)*BKT_INTRVL_A + BKT_MIN_SIZE_A)		\
   : ((IX) <= BKT_MAX_IX_B						\
      ? (((IX) - BKT_MIN_IX_B)*BKT_INTRVL_B + BKT_MIN_SIZE_B)		\
      : ((IX) <= BKT_MAX_IX_C						\
	 ? (((IX) - BKT_MIN_IX_C)*BKT_INTRVL_C + BKT_MIN_SIZE_C)	\
	 : (((IX) - BKT_MIN_IX_D)*(BAP)->bkt_intrvl_d + BKT_MIN_SIZE_D))))

#ifdef DEBUG

static int
BKT_IX(GFAllctr_t *gfallctr, Uint size)
{
    int ix;
    ASSERT(size >= MIN_BLK_SZ);

    ix = BKT_IX_(gfallctr, size);

    ASSERT(0 <= ix && ix <= BKT_MAX_IX_D);

    return ix;
}

static Uint
BKT_MIN_SZ(GFAllctr_t *gfallctr, int ix)
{
    Uint size;
    ASSERT(0 <= ix && ix <= BKT_MAX_IX_D);

    size = BKT_MIN_SZ_(gfallctr, ix);

#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
    ASSERT(ix == BKT_IX(gfallctr, size));
    ASSERT(size == MIN_BLK_SZ || ix - 1 == BKT_IX(gfallctr, size - 1));
#endif

    return size;
}

#else

#define BKT_IX BKT_IX_
#define BKT_MIN_SZ BKT_MIN_SZ_

#endif


/* Prototypes of callback functions */
static Block_t *	get_free_block		(Allctr_t *, Uint);
static void		link_free_block		(Allctr_t *, Block_t *);
static void		unlink_free_block	(Allctr_t *, Block_t *);
static void		update_last_aux_mbc	(Allctr_t *, Carrier_t *);
static Eterm		info_options		(Allctr_t *, char *, int *,
						 void *, Uint **, Uint *);
static void		init_atoms		(void);

#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
static void		check_block		(Allctr_t *, Block_t *,  int);
static void		check_mbc		(Allctr_t *, Carrier_t *);
#endif

static int atoms_initialized = 0;

void
erts_gfalc_init(void)
{
    atoms_initialized = 0;
}


Allctr_t *
erts_gfalc_start(GFAllctr_t *gfallctr,
		 GFAllctrInit_t *gfinit,
		 AllctrInit_t *init)
{
    GFAllctr_t nulled_state = {{0}};
    /* {{0}} is used instead of {0}, in order to avoid (an incorrect) gcc
       warning. gcc warns if {0} is used as initializer of a struct when
       the first member is a struct (not if, for example, the third member
       is a struct). */
    Allctr_t *allctr = (Allctr_t *) gfallctr;

    sys_memcpy((void *) gfallctr, (void *) &nulled_state, sizeof(GFAllctr_t));

    allctr->mbc_header_size		= sizeof(Carrier_t);
    allctr->min_mbc_size		= MIN_MBC_SZ;
    allctr->min_mbc_first_free_size	= MIN_MBC_FIRST_FREE_SZ;
    allctr->min_block_size		= sizeof(GFFreeBlock_t);


    allctr->vsn_str = ERTS_ALC_GF_ALLOC_VSN_STR;

    /* Callback functions */

    allctr->get_free_block		= get_free_block;
    allctr->link_free_block		= link_free_block;
    allctr->unlink_free_block		= unlink_free_block;
    allctr->info_options		= info_options;

    allctr->get_next_mbc_size		= NULL;
    allctr->creating_mbc		= update_last_aux_mbc;
    allctr->destroying_mbc		= update_last_aux_mbc;

    allctr->init_atoms			= init_atoms;

#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
    allctr->check_block			= check_block;
    allctr->check_mbc			= check_mbc;
#endif

    allctr->atoms_initialized		= 0;

    if (init->sbct > BKT_MIN_SIZE_D-1)
	gfallctr->bkt_intrvl_d =
	    UNIT_CEILING(((3*(init->sbct - BKT_MIN_SIZE_D - 1)
			   /(NO_OF_BKTS/4 - 1)) + 1)
			 / 2);
    if (gfallctr->bkt_intrvl_d < BKT_INTRVL_C)
	gfallctr->bkt_intrvl_d = BKT_INTRVL_C;
    gfallctr->bkt_max_size_d = ((NO_OF_BKTS/4)*gfallctr->bkt_intrvl_d
				+ BKT_MIN_SIZE_D
				- 1);

    gfallctr->max_blk_search		= (Uint) MAX(1, gfinit->mbsd);

    if (!erts_alcu_start(allctr, init))
	return NULL;

    if (allctr->min_block_size != MIN_BLK_SZ)
	return NULL;

    return allctr;
}

static int
find_bucket(BucketMask_t *bmask, int min_index)
{
    int min, mid, max;
    int sub_mask_ix, sub_bkt_ix;
    int ix = -1;

#undef  GET_MIN_BIT
#define GET_MIN_BIT(MinBit, BitMask, Min, Max)		\
    min = (Min);					\
    max = (Max);					\
    while(max != min) {					\
	mid = ((max - min) >> 1) + min;			\
	if((BitMask)					\
	   & (~(~((Uint) 0) << (mid + 1)))		\
	   & (~((Uint) 0) << min))			\
	    max = mid;					\
	else						\
	    min = mid + 1;				\
    }							\
    (MinBit) = min


    ASSERT(bmask->main < (((Uint) 1) << (MAX_SUB_MASK_IX+1)));

    sub_mask_ix = IX2SMIX(min_index);

    if ((bmask->main & (~((Uint) 0) << sub_mask_ix)) == 0)
	return -1;

    /* There exists a non empty bucket; find it... */

    if (bmask->main & (((Uint) 1) << sub_mask_ix)) {
	sub_bkt_ix = IX2SBIX(min_index);
	if ((bmask->sub[sub_mask_ix] & (~((Uint) 0) << sub_bkt_ix)) == 0) {
	    sub_mask_ix++;
	    sub_bkt_ix = 0;
	    if ((bmask->main & (~((Uint) 0)<< sub_mask_ix)) == 0)
		return -1;
	}
	else
	    goto find_sub_bkt_ix;
    }
    else {
	sub_mask_ix++;
	sub_bkt_ix = 0;
    }

    ASSERT(sub_mask_ix <= MAX_SUB_MASK_IX);
    /* Has to be a bit > sub_mask_ix */
    ASSERT(bmask->main & (~((Uint) 0) << (sub_mask_ix)));
    GET_MIN_BIT(sub_mask_ix, bmask->main, sub_mask_ix, MAX_SUB_MASK_IX);

 find_sub_bkt_ix:
    ASSERT(sub_mask_ix <= MAX_SUB_MASK_IX);
    ASSERT(sub_bkt_ix <= MAX_SUB_BKT_IX);

    if ((bmask->sub[sub_mask_ix] & (((Uint) 1) << sub_bkt_ix)) == 0) {
	ASSERT(sub_mask_ix + 1 <= MAX_SUB_BKT_IX);
	/* Has to be a bit > sub_bkt_ix */
	ASSERT(bmask->sub[sub_mask_ix] & (~((Uint) 0) << sub_bkt_ix));

	GET_MIN_BIT(sub_bkt_ix,
		    bmask->sub[sub_mask_ix],
		    sub_bkt_ix+1,
		    MAX_SUB_BKT_IX);

	ASSERT(sub_bkt_ix <= MAX_SUB_BKT_IX);
    }

    ix = MAKE_BKT_IX(sub_mask_ix, sub_bkt_ix);

    ASSERT(0 <= ix && ix < NO_OF_BKTS); 

    return ix;

#undef  GET_MIN_BIT