erl_alloc_util.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 memory allocator utility. This utility provides
 *              management of (multiple) memory segments, coalescing
 *              of free blocks, etc. Allocators are implemented by
 *              implementing a callback-interface which is called by
 *              this utility. The only task the callback-module has to
 *              perform is to supervise the free blocks.
 *
 * Author: 	Rickard Green
 */

/*
 * Alloc util will enforce 8 byte alignment if sys_alloc and mseg_alloc at
 * least enforces 8 byte alignment. If sys_alloc only enforces 4 byte
 * alignment then alloc util will do so too. 
 */

#ifdef HAVE_CONFIG_H
#  include "config.h"
#endif

#include "global.h"
#include "big.h"
#include "erl_mtrace.h"
#define GET_ERL_ALLOC_UTIL_IMPL
#include "erl_alloc_util.h"
#include "erl_mseg.h"
#include "erl_threads.h"

#if defined(ERTS_ALLOC_UTIL_HARD_DEBUG) && defined(__GNUC__)
#warning "* * * * * * * * * *"
#warning "* * * * * * * * * *"
#warning "* * NOTE:       * *"
#warning "* * Hard debug  * *"
#warning "* * is enabled! * *"
#warning "* * * * * * * * * *"
#warning "* * * * * * * * * *"
#endif

#define ALLOC_ZERO_EQ_NULL 0

static int atoms_initialized = 0;
static int initialized = 0;


#if HAVE_ERTS_MSEG

#define INV_MSEG_UNIT_MASK	((Uint) (mseg_unit_size - 1))
#define MSEG_UNIT_MASK		(~INV_MSEG_UNIT_MASK)
#define MSEG_UNIT_FLOOR(X)	((X) & MSEG_UNIT_MASK)
#define MSEG_UNIT_CEILING(X)	MSEG_UNIT_FLOOR((X) + INV_MSEG_UNIT_MASK)

#endif

#define INV_SYS_ALLOC_CARRIER_MASK	((Uint) (sys_alloc_carrier_size - 1))
#define SYS_ALLOC_CARRIER_MASK		(~INV_SYS_ALLOC_CARRIER_MASK)
#define SYS_ALLOC_CARRIER_FLOOR(X)	((X) & SYS_ALLOC_CARRIER_MASK)
#define SYS_ALLOC_CARRIER_CEILING(X) \
  SYS_ALLOC_CARRIER_FLOOR((X) + INV_SYS_ALLOC_CARRIER_MASK)

#undef ASSERT
#define ASSERT ASSERT_EXPR

#if 0
/* Can be useful for debugging */
#define MBC_REALLOC_ALWAYS_MOVES
#endif


/* alloc_util global parameters */
static Uint sys_alloc_carrier_size;
#if HAVE_ERTS_MSEG
static Uint max_mseg_carriers;
static Uint mseg_unit_size;
#endif

#define ONE_GIGA (1000000000)

#define INC_CC(CC) ((CC).no == ONE_GIGA - 1				\
		    ? ((CC).giga_no++, (CC).no = 0)			\
		    : (CC).no++)

#define DEC_CC(CC) ((CC).no == 0					\
		    ? ((CC).giga_no--, (CC).no = ONE_GIGA - 1)		\
		    : (CC).no--)

/* ... */

/* Blocks ... */

#define SBC_BLK_FTR_FLG		(((Uint) 1) << 0)
#define UNUSED1_BLK_FTR_FLG	(((Uint) 1) << 1)
#define UNUSED2_BLK_FTR_FLG	(((Uint) 1) << 2)

#define ABLK_HDR_SZ (sizeof(Block_t))
#define FBLK_FTR_SZ (sizeof(Uint))

#define UMEMSZ2BLKSZ(AP, SZ)						\
  (ABLK_HDR_SZ + (SZ) <= (AP)->min_block_size				\
   ? (AP)->min_block_size						\
   : UNIT_CEILING(ABLK_HDR_SZ + (SZ)))

#define UMEM2BLK(P) ((Block_t *) (((char *) (P)) - ABLK_HDR_SZ))
#define BLK2UMEM(P) ((void *)    (((char *) (P)) + ABLK_HDR_SZ))

#define PREV_BLK_SZ(B) \
  ((Uint) (*(((Uint *) (B)) - 1) & SZ_MASK))

#define SET_BLK_SZ_FTR(B, SZ) \
  (*((Uint *) (((char *) (B)) + (SZ) - sizeof(Uint))) = (SZ))

#define THIS_FREE_BLK_HDR_FLG 	(((Uint) 1) << 0)
#define PREV_FREE_BLK_HDR_FLG 	(((Uint) 1) << 1)
#define LAST_BLK_HDR_FLG 	(((Uint) 1) << 2)

#define SET_BLK_SZ(B, SZ) \
  (ASSERT(((SZ) & FLG_MASK) == 0), \
   (*((Block_t *) (B)) = ((*((Block_t *) (B)) & FLG_MASK) | (SZ))))
#define SET_BLK_FREE(B) \
  (*((Block_t *) (B)) |= THIS_FREE_BLK_HDR_FLG)
#define SET_BLK_ALLOCED(B) \
  (*((Block_t *) (B)) &= ~THIS_FREE_BLK_HDR_FLG)
#define SET_PREV_BLK_FREE(B) \
  (*((Block_t *) (B)) |= PREV_FREE_BLK_HDR_FLG)
#define SET_PREV_BLK_ALLOCED(B) \
  (*((Block_t *) (B)) &= ~PREV_FREE_BLK_HDR_FLG)
#define SET_LAST_BLK(B) \
  (*((Block_t *) (B)) |= LAST_BLK_HDR_FLG)
#define SET_NOT_LAST_BLK(B) \
  (*((Block_t *) (B)) &= ~LAST_BLK_HDR_FLG)

#define SBH_THIS_FREE		THIS_FREE_BLK_HDR_FLG
#define SBH_THIS_ALLOCED	((Uint) 0)
#define SBH_PREV_FREE		PREV_FREE_BLK_HDR_FLG
#define SBH_PREV_ALLOCED	((Uint) 0)
#define SBH_LAST_BLK		LAST_BLK_HDR_FLG
#define SBH_NOT_LAST_BLK	((Uint) 0)

#define SET_BLK_HDR(B, Sz, F) \
  (ASSERT(((Sz) & FLG_MASK) == 0), *((Block_t *) (B)) = ((Sz) | (F)))

#define BLK_UMEM_SZ(B) \
  (BLK_SZ(B) - (ABLK_HDR_SZ))
#define IS_PREV_BLK_FREE(B) \
  (*((Block_t *) (B)) & PREV_FREE_BLK_HDR_FLG)
#define IS_PREV_BLK_ALLOCED(B) \
  (!IS_PREV_BLK_FREE((B)))
#define IS_FREE_BLK(B) \
  (*((Block_t *) (B)) & THIS_FREE_BLK_HDR_FLG)
#define IS_ALLOCED_BLK(B) \
  (!IS_FREE_BLK((B)))  
#define IS_LAST_BLK(B) \
  (*((Block_t *) (B)) & LAST_BLK_HDR_FLG)
#define IS_NOT_LAST_BLK(B) \
  (!IS_LAST_BLK((B)))

#define GET_LAST_BLK_HDR_FLG(B) \
  (*((Block_t*) (B)) & LAST_BLK_HDR_FLG)
#define GET_THIS_FREE_BLK_HDR_FLG(B) \
  (*((Block_t*) (B)) & THIS_FREE_BLK_HDR_FLG)
#define GET_PREV_FREE_BLK_HDR_FLG(B) \
  (*((Block_t*) (B)) & PREV_FREE_BLK_HDR_FLG)

#define IS_FIRST_BLK(B) \
  (IS_PREV_BLK_FREE((B)) && (PREV_BLK_SZ((B)) == 0))
#define IS_NOT_FIRST_BLK(B) \
  (!IS_FIRST_BLK((B)))

#define SET_SBC_BLK_FTR(FTR) \
  ((FTR) = (0 | SBC_BLK_FTR_FLG))
#define SET_MBC_BLK_FTR(FTR) \
  ((FTR) = 0)

#define IS_SBC_BLK(B) \
  (IS_PREV_BLK_FREE((B)) && (((Uint *) (B))[-1] & SBC_BLK_FTR_FLG))
#define IS_MBC_BLK(B) \
  (!IS_SBC_BLK((B)))

#define NXT_BLK(B) \
  ((Block_t *) (((char *) (B)) + BLK_SZ((B))))
#define PREV_BLK(B) \
  ((Block_t *) (((char *) (B)) - PREV_BLK_SZ((B))))

/* Carriers ... */

#define MSEG_CARRIER_HDR_FLAG		(((Uint) 1) << 0)
#define SBC_CARRIER_HDR_FLAG		(((Uint) 1) << 1)

#define SBC_HDR_SZ \
  (UNIT_CEILING(sizeof(Carrier_t) + FBLK_FTR_SZ + ABLK_HDR_SZ) - ABLK_HDR_SZ)

#define SCH_SYS_ALLOC			0
#define SCH_MSEG			MSEG_CARRIER_HDR_FLAG
#define SCH_MBC				0
#define SCH_SBC				SBC_CARRIER_HDR_FLAG

#define SET_CARRIER_HDR(C, Sz, F) \
  (ASSERT(((Sz) & FLG_MASK) == 0), (C)->chdr = ((Sz) | (F)))

#define BLK2SBC(B) \
  ((Carrier_t *) (((char *) (B)) - SBC_HDR_SZ))
#define FBLK2MBC(AP, B) \
  ((Carrier_t *) (((char *) (B)) - (AP)->mbc_header_size))

#define MBC2FBLK(AP, P) \
  ((Block_t *) (((char *) (P)) + (AP)->mbc_header_size))
#define SBC2BLK(P) \
  ((Block_t *) (((char *) (P)) + SBC_HDR_SZ))
#define SBC2UMEM(P) \
  ((void *) (((char *) (P)) + (SBC_HDR_SZ + ABLK_HDR_SZ)))

#define IS_MSEG_CARRIER(C) \
  ((C)->chdr & MSEG_CARRIER_HDR_FLAG)
#define IS_SYS_ALLOC_CARRIER(C) \
  (!IS_MSEG_CARRIER((C)))
#define IS_SB_CARRIER(C) \
  ((C)->chdr & SBC_CARRIER_HDR_FLAG)
#define IS_MB_CARRIER(C) \
  (!IS_SB_CARRIER((C)))

#define SET_MSEG_CARRIER(C) \
  ((C)->chdr |= MSEG_CARRIER_HDR_FLAG)
#define SET_SYS_ALLOC_CARRIER(C) \
  ((C)->chdr &= ~MSEG_CARRIER_HDR_FLAG)
#define SET_SB_CARRIER(C) \
  ((C)->chdr |= SBC_CARRIER_HDR_FLAG)
#define SET_MB_CARRIER(C) \
  ((C)->chdr &= ~SBC_CARRIER_HDR_FLAG)

#define SET_CARRIER_SZ(C, SZ) \
  (ASSERT(((SZ) & FLG_MASK) == 0), \
   ((C)->chdr = ((C)->chdr & FLG_MASK) | (SZ)))

#define CFLG_SBC				(1 << 0)
#define CFLG_MBC				(1 << 1)
#define CFLG_FORCE_MSEG				(1 << 2)
#define CFLG_FORCE_SYS_ALLOC			(1 << 3)
#define CFLG_FORCE_SIZE				(1 << 4)
#define CFLG_MAIN_CARRIER			(1 << 5)

#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
static void check_blk_carrier(Allctr_t *, Block_t *);
#define HARD_CHECK_BLK_CARRIER(A, B)	check_blk_carrier((A), (B))
#else
#define HARD_CHECK_BLK_CARRIER(A, B)
#endif


/* Statistics updating ... */

#ifdef DEBUG
#define DEBUG_CHECK_CARRIER_NO_SZ(AP)					\
    ASSERT(((AP)->sbcs.curr_mseg.no && (AP)->sbcs.curr_mseg.size)	\
	   || (!(AP)->sbcs.curr_mseg.no && !(AP)->sbcs.curr_mseg.size));\
    ASSERT(((AP)->sbcs.curr_sys_alloc.no && (AP)->sbcs.curr_sys_alloc.size)\
	   || (!(AP)->sbcs.curr_sys_alloc.no && !(AP)->sbcs.curr_sys_alloc.size));\
    ASSERT(((AP)->mbcs.curr_mseg.no && (AP)->mbcs.curr_mseg.size)	\
	   || (!(AP)->mbcs.curr_mseg.no && !(AP)->mbcs.curr_mseg.size));\
    ASSERT(((AP)->mbcs.curr_sys_alloc.no && (AP)->mbcs.curr_sys_alloc.size)\
	   || (!(AP)->mbcs.curr_sys_alloc.no && !(AP)->mbcs.curr_sys_alloc.size))

#else
#define DEBUG_CHECK_CARRIER_NO_SZ(AP)
#endif

#define STAT_SBC_ALLOC(AP, BSZ)						\
    (AP)->sbcs.blocks.curr.size += (BSZ);				\
    if ((AP)->sbcs.blocks.max.size < (AP)->sbcs.blocks.curr.size)	\
	(AP)->sbcs.blocks.max.size = (AP)->sbcs.blocks.curr.size;	\
    if ((AP)->sbcs.max.no < ((AP)->sbcs.curr_mseg.no			\
			     + (AP)->sbcs.curr_sys_alloc.no))		\
	(AP)->sbcs.max.no = ((AP)->sbcs.curr_mseg.no			\
			     + (AP)->sbcs.curr_sys_alloc.no);		\
    if ((AP)->sbcs.max.size < ((AP)->sbcs.curr_mseg.size		\
			       + (AP)->sbcs.curr_sys_alloc.size))	\
	(AP)->sbcs.max.size = ((AP)->sbcs.curr_mseg.size		\
			       + (AP)->sbcs.curr_sys_alloc.size)

#define STAT_MSEG_SBC_ALLOC(AP, CSZ, BSZ)				\
do {									\
    (AP)->sbcs.curr_mseg.no++;						\
    (AP)->sbcs.curr_mseg.size += (CSZ);					\
    STAT_SBC_ALLOC((AP), (BSZ));					\
    DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
} while (0)

#define STAT_SYS_ALLOC_SBC_ALLOC(AP, CSZ, BSZ)				\
do {									\
    (AP)->sbcs.curr_sys_alloc.no++;					\
    (AP)->sbcs.curr_sys_alloc.size += (CSZ);				\
    STAT_SBC_ALLOC((AP), (BSZ));					\
    DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
} while (0)


#define STAT_SBC_FREE(AP, BSZ)						\
    ASSERT((AP)->sbcs.blocks.curr.size >= (BSZ));			\
    (AP)->sbcs.blocks.curr.size -= (BSZ)

#define STAT_MSEG_SBC_FREE(AP, CSZ, BSZ)				\
do {									\
    ASSERT((AP)->sbcs.curr_mseg.no > 0);				\
    (AP)->sbcs.curr_mseg.no--;						\
    ASSERT((AP)->sbcs.curr_mseg.size >= (CSZ));				\
    (AP)->sbcs.curr_mseg.size -= (CSZ);					\
    STAT_SBC_FREE((AP), (BSZ));						\
    DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
} while (0)

#define STAT_SYS_ALLOC_SBC_FREE(AP, CSZ, BSZ)				\
do {									\
    ASSERT((AP)->sbcs.curr_sys_alloc.no > 0);				\
    (AP)->sbcs.curr_sys_alloc.no--;					\
    ASSERT((AP)->sbcs.curr_sys_alloc.size >= (CSZ));			\
    (AP)->sbcs.curr_sys_alloc.size -= (CSZ);				\
    STAT_SBC_FREE((AP), (BSZ));						\
    DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
} while (0)

#define STAT_MBC_ALLOC(AP)						\
    if ((AP)->mbcs.max.no < ((AP)->mbcs.curr_mseg.no			\
			     + (AP)->mbcs.curr_sys_alloc.no))		\
	(AP)->mbcs.max.no = ((AP)->mbcs.curr_mseg.no			\
			     + (AP)->mbcs.curr_sys_alloc.no);		\
    if ((AP)->mbcs.max.size < ((AP)->mbcs.curr_mseg.size		\
			       + (AP)->mbcs.curr_sys_alloc.size))	\
	(AP)->mbcs.max.size = ((AP)->mbcs.curr_mseg.size		\
			       + (AP)->mbcs.curr_sys_alloc.size)


#define STAT_MSEG_MBC_ALLOC(AP, CSZ)					\
do {									\
    (AP)->mbcs.curr_mseg.no++;						\
    (AP)->mbcs.curr_mseg.size += (CSZ);					\
    STAT_MBC_ALLOC((AP));						\
    DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
} while (0)

#define STAT_SYS_ALLOC_MBC_ALLOC(AP, CSZ)				\
do {									\
    (AP)->mbcs.curr_sys_alloc.no++;					\
    (AP)->mbcs.curr_sys_alloc.size += (CSZ);				\
    STAT_MBC_ALLOC((AP));						\
    DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
} while (0)

#define STAT_MSEG_MBC_FREE(AP, CSZ)					\
do {									\
    ASSERT((AP)->mbcs.curr_mseg.no > 0);				\
    (AP)->mbcs.curr_mseg.no--;						\
    ASSERT((AP)->mbcs.curr_mseg.size >= (CSZ));				\
    (AP)->mbcs.curr_mseg.size -= (CSZ);					\
    DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
} while (0)

#define STAT_SYS_ALLOC_MBC_FREE(AP, CSZ)				\
do {									\
    ASSERT((AP)->mbcs.curr_sys_alloc.no > 0);				\
    (AP)->mbcs.curr_sys_alloc.no--;					\
    ASSERT((AP)->mbcs.curr_sys_alloc.size >= (CSZ));			\
    (AP)->mbcs.curr_sys_alloc.size -= (CSZ);				\
    DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
} while (0)

#define STAT_MBC_BLK_ALLOC(AP, BSZ)					\
do {									\
    (AP)->mbcs.blocks.curr.no++;					\
    if ((AP)->mbcs.blocks.max.no < (AP)->mbcs.blocks.curr.no)		\
	(AP)->mbcs.blocks.max.no = (AP)->mbcs.blocks.curr.no;		\
    (AP)->mbcs.blocks.curr.size += (BSZ);				\
    if ((AP)->mbcs.blocks.max.size < (AP)->mbcs.blocks.curr.size)	\
	(AP)->mbcs.blocks.max.size = (AP)->mbcs.blocks.curr.size;	\
} while (0)

#define STAT_MBC_BLK_FREE(AP, BSZ)					\
do {									\
    ASSERT((AP)->mbcs.blocks.curr.no > 0);				\
    (AP)->mbcs.blocks.curr.no--;					\
    ASSERT((AP)->mbcs.blocks.curr.size >= (BSZ));			\
    (AP)->mbcs.blocks.curr.size -= (BSZ);				\
} while (0)

/* Debug stuff... */
#ifdef DEBUG
static Uint carrier_alignment;
#define DEBUG_SAVE_ALIGNMENT(C)						\
do {									\
    Uint algnmnt__ = sizeof(Unit_t) - (((Uint) (C)) % sizeof(Unit_t));	\
    carrier_alignment = MIN(carrier_alignment, algnmnt__);		\
    ASSERT(((Uint) (C)) % sizeof(Uint) == 0);				\
} while (0)
#define DEBUG_CHECK_ALIGNMENT(P)					\
do {									\
    ASSERT(sizeof(Unit_t) - (((Uint) (P)) % sizeof(Unit_t))		\
	   >= carrier_alignment);					\
    ASSERT(((Uint) (P)) % sizeof(Uint) == 0);				\
} while (0)

#else
#define DEBUG_SAVE_ALIGNMENT(C)
#define DEBUG_CHECK_ALIGNMENT(P)
#endif

static void make_name_atoms(Allctr_t *allctr);


/* mseg ... */

#if HAVE_ERTS_MSEG

static ERTS_INLINE void *
alcu_mseg_alloc(Allctr_t *allctr, Uint *size_p)
{
    void *res;

    res = erts_mseg_alloc_opt(allctr->alloc_no, size_p, &allctr->mseg_opt);
    INC_CC(allctr->calls.mseg_alloc);
    return res;
}

static ERTS_INLINE void *
alcu_mseg_realloc(Allctr_t *allctr, void *seg, Uint old_size, Uint *new_size_p)
{
    void *res;

    res = erts_mseg_realloc_opt(allctr->alloc_no, seg, old_size, new_size_p,
				&allctr->mseg_opt);
    INC_CC(allctr->calls.mseg_realloc);
    return res;
}

static ERTS_INLINE void
alcu_mseg_dealloc(Allctr_t *allctr, void *seg, Uint size)
{
    erts_mseg_dealloc_opt(allctr->alloc_no, seg, size, &allctr->mseg_opt);
    INC_CC(allctr->calls.mseg_dealloc);
}

#endif

static ERTS_INLINE void *
alcu_sys_alloc(Allctr_t *allctr, Uint size)
{
    void *res;

    res = erts_sys_alloc(0, NULL, size);
    INC_CC(allctr->calls.sys_alloc);
    if (erts_mtrace_enabled)
	erts_mtrace_crr_alloc(res, allctr->alloc_no, ERTS_ALC_A_SYSTEM, size);
    return res;
}

static ERTS_INLINE void *
alcu_sys_realloc(Allctr_t *allctr, void *ptr, Uint size)
{
    void *res;

    res = erts_sys_realloc(0, NULL, ptr, size);
    INC_CC(allctr->calls.sys_realloc);
    if (erts_mtrace_enabled)
	erts_mtrace_crr_realloc(res,
				allctr->alloc_no,
				ERTS_ALC_A_SYSTEM,
				ptr,
				size);
    return res;
}

static ERTS_INLINE void
alcu_sys_free(Allctr_t *allctr, void *ptr)
{
    erts_sys_free(0, NULL, ptr);
    INC_CC(allctr->calls.sys_free);
    if (erts_mtrace_enabled)
	erts_mtrace_crr_free(allctr->alloc_no, ERTS_ALC_A_SYSTEM, ptr);
}

static Uint
get_next_mbc_size(Allctr_t *allctr)
{
    Uint size;
    int cs = (allctr->mbcs.curr_mseg.no
	      + allctr->mbcs.curr_sys_alloc.no
	      - (allctr->main_carrier ? 1 : 0));

    ASSERT(cs >= 0);
    ASSERT(allctr->largest_mbc_size >= allctr->smallest_mbc_size);

    if (cs >= allctr->mbc_growth_stages)
	size = allctr->largest_mbc_size;
    else
	size = ((cs*(allctr->largest_mbc_size - allctr->smallest_mbc_size)
		 / allctr->mbc_growth_stages)
		+ allctr->smallest_mbc_size);

    if (size < allctr->min_mbc_size)
	size = allctr->min_mbc_size;